（计算机应用技术专业论文）编程题自动评判中相关技术的研究与实现.pdf

_ 。， k i ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g r e s e a r c ha n d i m p l e m e n t a t i o no f r e l a t e d t e c h n o l o g i e si np r o g r a mj u d g i n g a u t o m a t i c a l l y c a n d i d a t e ：w a n gj i a n y i s u p e r v i s o r ：a s s o c i a t ep r o f g u oj i a n g h o n g a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：j a n u a r y ，2 0 1 0 d a t eo f0 r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y ， 。 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。， 作者( 签字) 渗肋 日期：m o l o 年月日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可酣在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者c 签字) ：耋拗 日期：幽驴年月么e l 导师( 签字) ： 幽口年1 月 即呜 哈尔滨下稗火学硕十学何论文 摘要 随着计算机技术在辅助教学中的飞速发展，计算机自动评判技术越来越 引起人们的关注。当今的评判系统中对客观题的评判技术近乎完善，但对主 观题的评判技术仍处于研究探索完善阶段。虽然目前已有一些程序评判系统 也投入使用，但绝大多只是对程序的输出结果进行评判，并没从程序理解语 义分析等角度考虑学生编写的程序，致使学生错误的程序得不到相应的分数。 本文针对当前编程题自动评判系统中的不足，设计了一种对编程题能够 实现自动评判的模型。模型中根据学生程序的可执行性采用动态和静态相结 合的评判方式。在动态评判过程中，本文使用代码执行可信度计算函数方法， 对学生程序的输出可信度进行计算并给出相应的分数；在静态评判过程中， 本文从程序理解角度出发，以系统依赖图作为程序的中间表示形式，根据系 统依赖图中控制依赖关系对程序进行分块加权，从而实现在程序结构上的评 判。同时，结合语义相似度等价转换技术，对程序进行规范化处理。使用类 二叉语法树描述程序中的表达式，并通过定义类二叉语法树的构造规则来消 除表达式结构的多样化。另外，还通过对表达式结构的比较完成程序变量的 归一化处理。 最后将该模型运用到实际编程题自动评判中进行实验，通过获得的实验 数据表明，此方法能够对学生程序进行自动评判，并有较强的实用价值。 关键词：自动评判；相似度；程序分析 一。 哈尔滨t 稗大学硕十学何论文 a b s t r a c t w i t ht h e r a p i de x p a n s i o n o fc o m p u t e rt e c h n i q u e si n c o m p u t e ra s s i s t e d i n s t r u c t i o n ，p e o p l ea r em o r ea n dm o r ei n t e r e s t e di nc o m p u t e ra u t o m a t i cj u d g i n g t e c h n i q u e t h ej u d g i n gt e c h n i q u e st oo b j e c t i v ep r o b l e m sa r ea l m o s tp e r f e c ti n c u r r e n tj u d g i n g s y s t e m ，b u t t o s u b j e c t i v ep r o b l e m sa r ea l s oi nr e s e a r c h i n g ， s t a g e a l t h o u g hs o m ep r o g r a mj u d g i n gs y s t e m sh a v eb e e np u ti n t oo p e r a t i o n ，m o s t o ft h e s eo n l yj u d g i n gt h eo u t p u tr e s u l t sw h i c hh a v en o tc o n s i d e r e dt h es t u d e n t s p r o g r a mf r o mt h ev i e wo fp r o g r a mu n d e r s t a n d i n ga n ds e m a n t i ca n a l y s i s t h e r e s u l ti st h a tt h es t u d e n t sw i l ln o tg e tt h ec o r r e s p o n d i n gs c o r ew h i tt h e i rm i s t a k e p r o g r a m s c o n t r a p o s i n gt h el a c ko fc u r r e n tp r o g r a ma u t o m a t i cj u d g i n gs y s t e m ，t h e s i s d e s i g n e dam o d e lw h i c hc a nr e a l i z et h ep r o g r a ma u t o m a t i cj u d g i n g t h ep a p e r a d o p tt h ei n t e g r a t em a n n e ro fa u t o m a t i ca n ds t a t i ca c c o r d i n gt ot h es t u d e n t s e x e c u t i v ep r o g r a m si nt h em o d e l i nt h ep r o c e s so f a u t o m a t i cj u d g i n g ，t h i sp a p e r c i t e dam e t h o do fc o d ee x e c u t i v er e l i a b i l t yf u n c t i o nw h i c hc o m p u t et h e c o r r e s p o n d i n gs c o r et h o u g hb yt h eo u t p u tr e l i a b i l t yo ft h es t u d e n t s p r o g r a m s i n t h ep r o c e s so fs t a t i cj u d g i n g ，t h i s p a p e rr e a l i z e d t h ej u d g i n go nt h ep r o g r a m s t r u c t u r ew h i c hf r o mt h ev i e wo fp r o g r a mu n d e r s t a n d i n g ，u s e ds y s t e md e p e n d e n c e g r a p ha st h em i d d l er e p r e s e n t e do ft h ep r o g r a ma n db l o c k e dw e i g h t i n gt ot h e p r o g r a ma c c o r d i n gt o t h ec o n t r o ld e p e n d e n c yo fs y s t e md e p e n d e n c eg r a p h s i m u l t a n e o u s l y ，i ts h o u l db es t a n d a r d i z i n gp r o c e s s e dt ot h ep r o g r a mt h a t b o n d w i t ht h e t e c h n i q u e o f s e m a n t i c s i m i l a r i t ye q u i v a l e n t t r a n s f o r m a t i o n s i m i l a r b i n a r y s y n t a xt r e e i su t i l i z e dt od e p i c tt h ep r o g r a me x p r e s s i o n ，r e m o v e dt h e d i v e r s i f i c a t i o no fe x p r e s s i o ns t r u c t u r et h o u g hb yf o r m a t i o nr u l eo ft h es i m i l a r b i n a r y s y n t a xt r e e a d d i t i o n a l l y ，i n o r d e rt on o r m a l i z i n gp r o c e s s t h ep r o g r a m 哈尔滨犟火学硕十学位论文 v a r i a b l e ，w en e e dt oc o m p a r et h ee x p r e s s i o ns t r u c t u r e f i n a l l y ，w eu t i l i z e dt h em o d e lt ot h ea c t u a lp r o g r a ma u t o m a t i cj u d g i n gi n o r d e rt oe x p e r i m e n t t h er e s u l ts h o wt h a tt h i sm e t h o dc a nr e a l i z et h ea u t o m a t i c j u d g i n gt ot h es t u d e n t s p r o g r a m sa n dg a v eab e t t e ru t i l i t yv a l u e k e y w o r d s ：a u t o m a t i cj u d g i n g ；s i m i l a r i t y ；p r o g r a ma n a l y s i s 产 哈尔滨下秤大学硕十学何论文 目录 第1 章绪论1 1 1 研究背景意义1 1 2 国内外研究现状2 1 3 论文研究内容5 1 4 论文内容安排6 第2 章相关技术概述7 2 1 程序分析相关技术7 2 1 1 词法与语法分析“7 2 2 3 信息流分析技术7 2 1 4 程序依赖相关概念8 2 2 代码相似度度量技术概述1 1 2 2 1 属性计数度量技术1 2 2 2 2 结构度量技术1 3 2 2 3 其它度量技术1 4 2 2 4 相似度的计算方法1 5 2 3 本章小结1 6 第3 章程序静态评判技术研究1 8 3 1 程序代码相似度比较1 8 3 1 1 代码相似度比较算法1 8 3 1 2 算法的应用不足分析2 1 3 1 3 代码分块加权处理方法2 2 3 1 4 代码块i 日j 比较处理方法2 6 3 2 代码多样化消除处理3 0 3 2 1 代码书写的规范化处理3 0 产 一 哈尔滨f 稃人学硕十学何论文 3 2 2 表达式结构多样化消除3 4 3 2 3 中间变量的消除3 6 3 2 4 变量的归一化3 7 3 3 本章小结3 8 第4 章程序评判模型的设计与实现3 9 4 1 评判模型结构设计3 9 4 2 各组成模块的功能及实现4 0 4 2 1 程序检测模块4 0 4 2 2 代码修复模块4 1 4 2 3 动态评判模块4 3 4 2 4 静态评判模块4 5 4 3 实验分析4 6 4 3 1 实例解析4 7 4 3 2 实验数据5 1 4 3 3 实验结果分析5 2 4 4 4 实验影响因子5 3 4 4 本章小结5 4 结论”5 5 参考文献5 7 攻读硕士学位期间发表的论文和取得的科研成果6 1 致j 射”6 2 广 哈尔滨t 稗大学硕十学位论文 第1 章绪论 1 1 研究背景意义 自计算机问世以来，它像蜘蛛网一样不断扩散蔓延到世界上的各个角落、 渗透到每一个行业。当计算机应用技术涌入到教育教学领域时，传统的教学 方式逐渐转变为人机交互式教学模式。在过去的几十年里，计算机大多以多 媒体的身份被教育界所采纳，从起初的幻灯片、投影仪到现在的多方位立体 教学，计算机已经不仅仅只是简单的辅助应用工具，已经成功的演变成一个 “助教”的角色，从而大大减轻了教师们的负担。 随着计算机辅助处理、多媒体以及计算机网络等技术的飞速发展和广泛 应用，其应用在教育教学上的比重也随之逐渐加大，计算机已不再单纯只做 为一个小角色出现，而是占据着更为重要的地位。c a a ( c o m p u t e ra s s i s t e d a s s e s s m e n t ) 研究组织的成立，标志着计算机教育应用技术已成为当前较为 炙手可热的研究课题。当计算机融入到教学考试阅卷这个环节时，它的价值 体现在不但可以解放教师们的生产力，更为重要的是，它在改善由于教师疲 劳度而引起的评阅准确率下降状况的同时，也能达到相对客观公正的目的。 但不同题型在阅卷过程中的难易程度也随之不同，目前，如选择题、判断题 等这类答案较易被统一的客观题，以及客观性比较强的填空题的自动评判技 术几尽成熟，而对于最能体现学生知识掌握程度和运用程度的主观题的自动 评判一直都不够完善，仍处于探索完善阶段。其主要原因是由于主观题的灵 活多变的答题特点以及解答过程的不确定性和复杂性，使针对主观题的评判 技术的难度大大加深。 编程题的自动评判作为主观题自动评判的一个分支研究近几年相对发展 较热。由于程序设计语言相对于自然语言来说，有严格的书写和表示形式， 使程序设计语言的评判过程较自然语言评判相对容易一些。一些专家和学者 开始纷纷投入到对程序设计语言的自动评判技术的研究上来，希望能从中获 1 哈尔滨r 稃大学硕十学何论文 得启示以便推广到整个主观题自动评判过程中来。但毕竟计算机仍无法完全 取代人脑，对于很多主观因素无法像人脑那样很好的识别出来，所以目前的 对编程题的研究过程仍处于探索细化及完善阶段。 1 2 国内外研究现状 早在上个世纪六十年代初期，国外的一些专家和学者就开始着手针对主 观题进行自动评判，但研究对象是针对于自然语言书写的主观题的评阅。而 此后的几十年里，随着对评判技术的深入研究与横向扩张，开始蔓延到不同 领域的系统，并取得了相对不错的成果。 起初实现对自然语言处理系统的是e l l i sp a g e 开发的p e g ( p r o j e c te s s a y g r a d e ) 系统。该系统通过对自然语言中内在特征量的采集，得到量化后的结 果，然后根据量化的结果经行评判i l 】。虽然p e g 在当时的评判过程中取得了 相对较高的准确率，但它仅仅是一种对文本撰写风格测评，并且单纯依靠统 计方法来评定文本的质量不但没有用到深入的自然语言处理技术，也没有考 虑到词汇的语义。而后出现的l s a t n 系统是一种近似于相似度属性度量研究 的系统，系统将自然语言文本转化成一个空间向量，列为文本的向量，行为 文本的特征向量。然后将文本产生的矩阵与标准答案文本产生的矩阵运用“距 离公式”进行计算，通过计算两个文本之间的距离来确定主观题的分值。l s a 适合范围是篇幅较长的文本之间的相似度度量，但对于长度较短或是只有个 别词语的文本匹配准确较低。e r a t e r t 3 l 主要采用整体评分策略，从写作风格、 修辞等角度将系统划分为句法分析模块、篇章分析模块、内容分析模块、评 分模型建模模块和评分模块五个模块，然后计算出每个模块对应的分值，最 一 。 后将这些分值统一调整后给出最终的文本成绩。这种系统的缺陷是需要大量 的评判数据来支持评分模块，并且不存在正确或是错误的答案，对于需要判 断结果正确与否而给出相应成绩之类的题目e r a t e r 系统就显得力不从心。后 来出现了一种基于语义的自动评分系统a t m p l ，a t m 系统是一种适用于那些 标准答案简短并且较为明确的考题的自动教学辅助系统。该系统引入了词库 2 产 哈尔滨r 秤大学硕十学何论文 的概念，使系统可以针对概念的同义词以及替代词进行识别，增加了系统的 识别能力和准确率。a t m 系统提供了一个可进行扩充规则的语法分析器，该 分析器能够对语法错综复杂的句子进行分析，即便是句子的语法有歧义的同 样能够得到相应的处理。这就要求系统需要较强的语法及语义分析能力，相 应的也就加大了系统的实现难度。a u t o m a r k t s l 系统主要是通过对考生答案中 正确信息的提取而相应评判的，也就是从学生答案中找到与标准答案相关的 信息就可以判断该题目为正确的。这种评分技术只关心标准答案信息在考生 给出的答案中存在与否，而对除了正确答案以外的信息视而不见，致使那些 涵盖了错误信息的答案可以逃之天天，这与人工评判中发现错误信息并扣出 相应的分数有一定的出入。 随着对自然语言阅卷处理的研究深入与横向拓展，国内外的一些专家学 者在研究自然语言处理的同时也开始致力于对其它形式的语言的主观题评阅 技术研究上来，对于使用机器语言书写的编程题自动评判技术也随之发展起 来。针对编程的评判方法的不同，目前所采用的评判策略大致可以分为动态 评分策略和静态评分策略两类1 6 1 。 动态评分策略主要是将事先准备好的数据包或者说是测试集，按照某种 特定的方式录入到经过编译处理的源程序中，通过对输出结果的正确性分析 给出相应的分数。目前以这种评判策略的国外典型代表系统有t r y 川，p s g e i s j 和b a g s i g l 系统等等。这种评判策略的缺陷在于：由于对编译器的依赖性，需 要学生源代码必须通过编译，这就导致一些由于某些词法或语法错误而引起 的无法通过编译的源程序得不到正常的评判。并且，该评判方法对源程序的 输出结果要求相对严格，对于输出结果有描述性语言的结果匹配不甚理想。 而静态评判策略是当前研究学者相对比较感兴趣的评判策略。，该方法以 编译原理的思想作为基础对学生程序如何编写实现进行理解分析，归纳程序 中的关键信息，根据所获信息给出学生程序应得分数。 目前，国外采用静态评判策略的系统有a s s y s t - o i 系统、k n o t s i 1 系统以 及v e r i l o gl o g i s c o p e l l 2 i 系统等。这些系统均通过对源程序的属性特征或者说是 3 产 冬 哈尔滨t 稃大学硕十学何论文 物理特征的度量来对学生程序经行评判。由于一个程序的物理特征是个定值， 如：操作符个数、代码长度等。通过对这些特征量的记录来衡量一个程序的 分值多少。 同时，国内也有一部分学者通过对编程题自动评判的研究为该技术的完 善做出相应的贡献。 沈阳工业大学的孙坤在学位论文中设计了一套自动组卷及评阅系统1 6 1 ， 该系统在生成试卷的同时可以通过学生的作答结果自动的评判出成绩。该系 统虽然使用了静态评判的方式对学生程序进行评判，但在评判过程中，系统 只能针对学生程序中一些较小的错误给出相应的分数。尽管在其中也使用了 对关键语句检索进行评判的方法，但实用范围有一定的局限性。 中南大学的佘石泉提出使用适当的正则表达式来描述得分点，然后根据 此正则表达式来对学生的程序进行评价【- 5 l 。利用正则表达式来描述程序的得 分点，其实质与阅卷模型中所提到的模板程序有相似之处。其不同点是正则 表达式的描述把程序拆开成为以得分点为单位的许多独立的模块，从而在考 生的程序中去查找这些模块是否存在，而不是拿整个程序进行完全匹配。相 比之下，这种方法较为灵活且类似于人工阅卷。 上述的评判系统都存在一个共同的不足之处：这些评判策略虽然有一定 的科学根据，但只处于对程序的量值、以及语句的静态检索的考虑上，没有 对程序内部结构及语义特征等特点进行剖析，这也就很难给出相对合理的分 数。在当前的静态评判策略中较为成型的评判模型有两种：一种是基于程序 理解的评判模型1 1 3 1 ，另一种是基于语义相似度的评判模型1 4 l 。 1 、基于程序理解的评判模型 程序理解是软件逆向工程里的一个重要研究领域，它通过对程序进行静 态分析、抽象和推理来获取信息。哈尔滨工业大学的李永浩【”l 提出从编程题 自动评判所要解决的核心问题以及主要任务来看，是可以通过程序理解的基 本原理和方法来解决评判中的相应问题的。文献中提出了一套基于程序理解 的编程题自动评判策略，其主要思想如下： 4 z 瓤 哈尔滨t 稗大学硕十学何论文 ( 1 ) 将学生程序以及模板程序都转化成各自的系统依赖图( s d g ) 。 ( 2 ) 通过对s d g 的标准化处理，来实现代码标准化的统一。 ( 3 ) 对学生程序和模板程序从规模、结构、深度以及知识应用四个层次上 进行匹配，根据匹配程度给出相应的分数。 这种方法主要是利用层次结构分析，通过对程序的逆向分析得到程序的 结构信息，并将其用图形化方式表示出来，虽然便于理解程序的内部结构及 逻辑关系，但侧重点在于对程序结构的理解，没能做到较精确地查看程序的 正确性。 2 、基于语义相似度的评判模型。 文献 1 4 】中所提出的基于语义相似度的评判模型，其思想是对程序中具 有相同语义的不同表达形式进行语义等价替换，然后对学生程序与模板程序 进行语义相似度匹配，匹配程度越高，相对应的学生程序分数越高。该方法 同样以s d g 为程序的语义表示形式，认为具有等价的s d g 的两个程序具有 等价的语义。使用一系列语义等价转换规则对s d g 进行标准化处理。通过获 得两个程序的系统依赖图的匹配程度给出最终分数。该模型虽然在功能上较 上一个模型有了很大的改进和完善，但对匹配模板质量要求过高，容易造成 正确的程序无法完全匹配而得到满分。 1 3 论文研究内容 本文针对计算机基础语言c 语言研究设计了一套能够对编程题进行自动 评判模型。模型采用动态评判和静态评判相结合的评判方式，同时嵌入了程 序理解、相似度匹配、执行可信度计算以及代码多样化消除等技术对学生程 序进行评判。 在评判过程中，对学生程序通过编译器编译时提示的错误信息统计分类， 并采用能改即改，尽最大可能修改的原则进行对学生程序修复。 在动态评判过程中，系统通过对代码的输出可信度的计算，对所进行动 态评判的程序给出相应的分数。 5 ， t 哈尔滨t 稃大学硕十学何论文 在静态评判过程中，本文在程序理解评判模型和语义分析评判模型基础 之上，模拟人工评判思维方式，对学生程序和模板程序进行最大相似度匹配。 在此过程中结合了程序分析、代码相似度度量以及代码多样化消除等技术对 学生程序进行剖析、分解及匹配等过程，最终给出相应分数。 同时，为了便于学生程序和模板程序进行匹配，本文用类二叉语法树来 表示程序中的表达式。并提出了类二叉语法树定义以及构造规则，以此消除 程序中表达式书写的多样化。并且，通过对类二叉语法树的比较达到变量的 归一处理的目的。 1 4 论文内容安排 本文共分为四章，各章节的内容编排如下： 第1 章主要介绍了编程题自动评判的研究背景及研究意义。对国内外研 究现状做了描述，同时指明了当前在该领域上的系统存在的不足。最后介绍 了本文研究的主要内容。 第2 章对本课题所涉及的相关知识做了相应的介绍。首先给出程序分析 中的相关技术以及概念，然后阐述了代码相似度度量技术的分类以及相似度 计算方法。 第3 章首先阐述了静态评判过程所使用的技术，并针对技术应用上的不 足做出相应的改进。然后定义了代码多样化消除规则及算法实现描述。 第4 章对评判模型中各模块功能及实现做了介绍。并在实验分析环节， 给出了自动评判的演示过程及实验数据分析。 6 一 哈尔滨t 稗大学硕十学何论文 第2 章相关技术概述 对学生程序进行评判就应从学生如何完成程序编写任务的角度理解学生 程序，需要对学生程序的内部结构进行分析获得关键信息，并通过与模板程 序之间的代码相似程度的计算给出相应分数。本章给出模型中所涉及到的相 关技术的描述。 2 1 程序分析相关技术 程序分析技术是以程序为处理对象，按需求对其进行各种分析的方法。 程序分析在程序理解方面有着重要的应用。程序分析中所涉及的概念很多， 本文只对所用的分析技术给出相关定义。 2 1 1 词法与语法分析 词法分析的主要任务是形成一个个单词序列以及错误处理，并将生成单 词序列用以语法分析。语法分析【1 6 l 主要任务是根据语言的语法规则，分析源 程序的语法结构，并在分析过程中，对源程序进行语法正确性检查，根据 语法规则对错误信息进行处理。 2 1 2 信息流分析技术 对于程序完成的功能以及完成的具体过程仅对程序进行词法分析和语法 分析是不够的，还需要通过控制流分析建立过程内部的控制层次，通过数据 流分析确定对程序数据操作的信息以达到对程序内部信息理解的目的。 定义2 1 信息流1 1 8 - 2 0 l ：在系统程序执行过程中，如果变量v l 的取值影响了 变量v 2 的取值，则认为有信息流从变量v - 流向变量v 2 ，简单记为v 1 _ v 2 。一 条信息流可以用一个四元组来表示： ( s ，o p ，v 1 v 2 ) s x o p x v x v 。其中，s 是主体的集合；o p 是操作的集合：v 是变量的集合，它表示主体s 执行0 p 7 产 哈尔滨丁稃大学硕十学位论文 操作引起从变量v 1 流向变量v 2 的信息流；v 1 和v 2 分别称为信息流源点变量 和终点变量。根据选取程序中的分析信息不同，可以将信息流分析分为控制 流分析和数据流分析两类。 1 、控制流分析概述 控制流分析主要是把程序源代码转换成程序的控制流图，并弄清程序每 条语句执行顺序。为语句间的控制依赖关系和数据依赖关系的确立奠定基础。 控制流分析主要有两种方法：第一种方法是利用必经点找到程序中的环， 然后对环添加一些简单注释。这种方法对于使用迭代数据流分析的优化器或 只对子程序中环感兴趣的分析是足够的：第二种方法成为区间分析，包括分 析子程序的整体结构，然后将其分解为可嵌套的区域，称为区间。 2 、数据流分析技术 数据流分析1 2 1 1 是通过对程序中对语义信息的收集并用代数的方法来确定 变量的定义和使用情况。数据流分析的优点在于更利于对程序的理解分析， 在程序不用实际运行的情况下就能够了解程序在运行时将要发生的行为。简 而言之，数据流可以看作是信息收集的过程，这些信息主要是指程序中数据 的定义、数据的利用情况以及数据之间的依赖关系等各方面信息1 2 2 1 。数据分 析通常是在控制流分析技术执行了程序基本块的划分以及控制流图构造完成 之后进行的。 数据流分析的目的是为了计算机分析程序在生成数据方面的行为，通常 用于程序优化，及为程序优化建立环境。最容易也是最广泛使用的方法是对 控制流进行循环分析，称为迭代数据流分析。另一种方法是省略控制流图， 直接对抽象语法树进行分析，称为语法制导的数据流分析。 信息流分析技术在程序理解方面起着非常重要的作用，通过对程序内部 结构的分析，可以建立程序的依赖关系，为后面的系统依赖图生成提供基础。 2 1 3 程序依赖相关概念 通过信息流分析技术中的控制流分析和数据流分析，能够得到隐含在语 8 哈尔滨t 稗大学硕十学何论文 i i i i i i i j i i i i 薯i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 置i i i i i i i i 鼍i 一 句之间的依赖关系，这种依赖关系称为程序依赖关系。在程序依赖关系中， 数据依赖代表了程序中各个操作语句之间的数据传递情况，控制依赖则表示 程序中的语句之间控制关系。为了方便说明，下面给出了程序依赖中的基本 定义。 定义2 1 图：图的定义通常是用一个三元组( v ( g ) ，e ( g ) ，九) 来表示，其中v ( g ) 表示结点的非空集合，e ( g ) 表示边的集合，九表示 从边集合e ( g ) 结点无序偶( 有序偶) 集合上的一个映射函数。图也可以用 图形来表示，当把图中边集e ( g ) 中的一个元素e i ( e i e ( g ) ) 看成一个 总是对应两个结点的边时，图就可以简记为g = ( v ，e ) ，其中v 是同样是表 示结点非空集合，e 表示结点之间相连的边集。 定义2 2 无向图、有向图：用来表示无序偶结点( v i ，v k ) 相关联的边e i ( e l e e ( g ) ) 称为无向边；用来表示有序偶结点( v i ，v k ) 相关联的边e i ( e i e ( g ) ) 称为无向边，这时，结点v i 表示边e i 的起始结点，结点v k 表示边e i 的终 止结点。对应的每条边都为无向边的图称为无向图，每一条边都为有向边的 图称为有向图。 定义2 3 逆图：逆图g = ( v ，e ) 是指把有向图g = ( v ，e ) 中的所有 有向边的方向反向得到的有向图。即在逆图中，v = v ，e = ( v k ，v i ) i ( v l ，v k ) e ) 。 定义2 4 若下列两个条件满足，则结点s l 控制流直接依赖于结点s 2 ，记为 c d ( s 2 ，s 1 ) 。 ( 1 ) 结点s 2 与结点s 1 间存在一可执行路径p a t h ： ( 2 ) 对p a t h 上每个结点s ( s = s s 2 ) 都有p o s t d ( s ，s 1 ) ； 定义2 5 控制流图c f g 【掘2 8 l ：程序p 的控制流图是一有向图，可用四元组 ( s ，e ，s 。咖，s 。姬。) 表示，s 是语句结点集，程序中的每条语句都对应图中 的一个结点；边集e = ( s t ，s 2 ) ls l ，s 2 e s ，s l 执行后，可能立即执行s 2 】i ； s e n t r y 和s e x i t 分别为程序的入口和出口结点，它们在控制流图中是唯一的。 定义2 6 数据依赖：设语句结点s 1 与语句结点s 2 是程序p 中两个语句， q 哈尔滨t 稃大学硕十学何论文 若存在变量v 满足d d v ( s l ，s 2 ，v ) ，则称语句结点s 1 数据依赖于结点s 2 ， 记为d d ( s 1 ，s 2 ) 。 定义2 7 设语句结点s 1 与语句结点s 2 为控制流图中的两个结点，v 为 一个变量，若满足下列三个条件，则称语句结点s 1 关于变量v 数据流直接依 赖于语句结点s 2 ，记为d d v ( s 1 ，s 2 ，v ) 。 ( 1 ) 语句结点s 2 对变量v 进行了定义，即v d e f ( s 2 ) ； ( 2 ) 语句结点s 1 执行时使用了v 的值，即v r e f ( s 1 ) ； ( 3 ) 语句结点s 2 与语句结点s 1 间存在一可执行路径p a t h = ( s 1 ，s 2 ， s n ) ，且在此路径上没有语句对变量v 进行重新定义。 下面又给出了在构建程序依赖图过程中所用的相关概念的定义。 定义2 8 直接前驱，直接后继：若( s 1 ，s 2 ) e ，则称语句结点s 1 是语 句结点s 2 的直接前驱结点，语句结点s 2 是语句结点s 1 的直接后继结点，记为 p r e ( s 1 ，s 2 ) ；语句s 的所有直接前驱结点组成的集合称为s 的直接前驱结点 集，记为p r e d ( s ) ；语句s 的所有直接后继结点的集合称为语句s 的直接后继 结点集，记为s u c c ( s ) 。 定义2 9 可执行路径：设路径p a t h = ( s l ，s 2 ，s n ) 为控制流图c f g 中一个语句序列，在这条路径中，如果p r e ( s i ，s i + 1 ) ，( i = 1 ，2 ，n 1 ) ， 则称p a t h = ( s l ，s 2 ，s 。) 为控制流图c f g 中一条可执行路径。 定义2 1 0 前驱结点：在控制流图c f g 中，若从结点s m 到结点s n ，之间存 在一个可执行路径p a t h = ( s m ，s l ，s k ，s n ) ，( k = o ) ，则称结点s m 是 结点s 。的前驱结点，记作p r e d ( s m ，s n ) 。 定义2 1 1 后必经点：如果从结点s 2 到程序出口结点s 。x i 。的每条路径都必 须经过结点s 1 ，则称结点s l 为结点s 2 的一个后必经点，记为p o s t d ( s 2 ，s 1 ) 结点s 的所有后支配结点组成的集合记为p o s t d ( s ) 。 定义2 1 2 程序依赖匿 p d g ( p r o g r a md e p e n d e n c yg r a p h ) 1 2 6 1 ：g = ( n ，e ， s 。仃y ，s e x i t ) 是c f gg = ( n ，e ，s 。s 。i t ) 的一个变形，节点和边分别满 足以下关系：n = n ，s e n t r y - s 。t r v ，s e x i t - - - - s 。”e = e d d ue c d 。其中e d d 表示 1 0 哈尔滨下烈大学硕十学何论文 数据依赖边，e c r , 表示控制依赖边，是通过对g 进行数据流分析和控制流分析 得到的边。 从程序依赖图定义可以看出p d g 是控制流图通过一定的变形得到的结构 图型，是从控制流图中去掉了控制流边，又增加了控制依赖和数据依赖边以 后生成的图。显然程序流图综合了控制依赖和数据依赖的优点，既可以表示 出数据依赖关系同时也能提供控制关系。程序依赖图是源代码的一种抽象的 图形表示形式，在程序依赖图中，图的每个节点代表着的是源代码的每条语 句，图中的边是有向边，表示程序的数据和控制依赖关系。 2 2 代码相似度度量技术概述 定义2 1 3 相似性1 2 9 1 ：相似性可以定义为用于对两个比较对象之间是否存 在一些内在联系或相关联性而引起的这两个对象表现形式上的一致的定性衡 量的概念，起初相似性的定义从文本相似而来，后来衍伸到代码相似上。 定义2 1 4 相似度1 3 0 1 ：用于相关数值的表示出两个比较对象之间的相关联 性的程度，对象主要指文本相似和代码相似。这个数值是通过对两个源程序 之间相似程度的检测求得的。一般使用一个表示范围在【0 ，1 】之间的小数或 【o ，1 0 0 的百分比值s i m 来表示相似程度。s i m 的数值越大，就表示两段源程 序代码的相关联性越高，即相似程度越高；反之，则表示两段源程序之间的 关联性越低。 代码相似度计算1 3 1 1 公式：现有两个程序段s 和t ，s = s l ，s 2 ，s m ) ， s 1 ，s 2 ，s m 表示s 的组成元素。同理，t 由元素t l ，t 2 ，t n 同样用集 合 t l ，t 2 ，t n ) 表示。这里的元素s i ( 1 - i _ m ) 和t j ( 1 - j = n ) 表示软件s 和 t 的一行或一段代码。用r s 来表示s 与t 之间所有匹配元素的集合，即 r s = ( s i ，t j ) is l = t j ，其中l = i = m ，1 - j = n 这里r s c _ s x t ，那么与r s 相关的s 和t 的相似度s i m ( s ，t ) 的计算公式为： s i m ( s ，t ) = 刚坠坐堡：掣掣堕堡型 ( 2 1 ) ls i + iti 哈尔滨t 程大学硕十学位论文 ( 1 = i = m 且1 - j = n ) 从相似度计算公式中不难看出，s 与t 之间的相似度是通过一个比值得 到的，在待比的两个程序大小一定的情况下，而这个比值大小的决定性因素 是r s 中元素的个数多少。如果r s 较大，s i m 的值就将较大；当s 和t 完全 匹配的时候，s i m ( s ，t ) = 1 ；反之，s i m 的值越小，当v ( i ，j ) 都有s i t j ， 即r s = 时， 困 则s i m = 0 。 图2 1 程序段s 与程序段t 相似性示意图 代码相似度度量从度量方法上大致可以分为两大类1 3 2 j ：一类是属性计数 度量技术，另一类是结构度量技术。 2 2 1 属性计数度量技术 属性计数度量技术刚主要是通过对代码源程序中那些能够反映一个程序 基本特征的属性的统计，这些属性通常是指程序内在的性质，能够从程序代 码中提取出来不随表达式变化而改变的特征。将统计出来的属性结果进行比 较最终得到两个程序的相似程度。而程序的属性特征可以分为两类：一类是 不可度量的，例如程序使用何种编程语言；另一种是可度量的，如程序代码 长度、代码行数、以及程序中的操作数个数等等，这些是可以定量的反映出 程序的特征的。属性计数度量方法实质上是对程序的量纲的统计比较，并没 1 2 哈尔滨t 稃大学硕十学佗论文 有深入到程序的结构上的比较。 第一个提出用代码属性计数度量技术的是m h a l s t e a d l 弘l 在十九世纪七十 年代中期提出的，h a l s t e a d 度量是基于程序源代码的。m h a l s t e a d 认为任何 一个程序代码都能够识别出它的所有变量以及常量等操作数；同时也可以统 计出所有的操作符，即影响操作数的值或顺序的符号或符号组合。操作符和 操作数统称为源代码的标识符。程序源代码中的可测量的属性部分主要就是 有这些信息组成。并且这些属性不易随程序表达形式改变而改变，即使改变 也是少数的。 m h a l s t e a d 给出的代码程序的四个度量属性值： ，71 ：代表源程序代码中唯一的操作符个数； ，72 ：代表源程序代码中唯一的操作数个数； n 1 ：代表源程序代码中总的操作符个数； n 2 ：代表源程序代码中总的操作数个数。 而后h a l s t e a d 根据这四个基本属性，又定义了，7 = r