（计算机应用技术专业论文）程序设计作业的测评技术研究.pdf

ad i s s e r t a t i o ns u b m i t t e dt og u a n g d o n g u n i v e r s i t yo f t e c h n o l o g yf o r t h ed e g r e eo fm a s t e ro fe n g i n e e r i n gs c i e n c e r e s e a r c ho np r o g r a md e s i g ne v a l u a t i n g t e c h n o l o g y m a s t e rc a n d i d a t e ：h u a n gj i e s h e n g s u p e r v i s o r ：p r o f w uw e i m i n m a y2 0 1 0 f a c u l t yo fc o m p u t e r g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a 。5 10 0 0 6 舢0舢9 舢7m 5舢4 舢乃iiy 摘要 摘要 随着计算机与网络技术的提高与普及，计算机机考、在线测试等广泛应用于 社会化考试及网络教育中。随之而来的计算机辅助测评( 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 ) 技术也受到了更多的关注。传统的计算机辅助测评技术更多的应用于 标准化考试，对客观题提供了高效便捷的测评。但对于灵活性和创造性较强的程 序作业测评，一直以来都更多的依靠人工评判。 本文通过对现有程序代码相似度技术的研究与分析。经过对多种不同测评技 术的分析，在现有的代码相似度度量技术基础上进行改进。在现有程序代码相似 度的度量技术中，主要有三大类测评技术，第一类是基于程序属性技术的度量， 包括应用明考夫斯基距离、余弦定理距离等；第二类是基于程序结构的度量，包 括有程序切片度量技术、圈复杂度度量技术等；第三类是基于字符串匹配技术的 度量，包括有动态规划法、基于最长公共子序列度量、基于最长公共予串度量、 基于编辑距离度量等。每种度量方法均有其各自的优缺点，单独使用每种度量技 术均有其不足之处，因此需对度量技术进行改进。 本文主要针对广东工业大学计算机学院可视计算实验室开发的a n y v i e w c 程 序作业系统进行测评技术的扩展研究。首先，对a n y v i e w c 现有编译器扩展程序 属性分析抽取模块，基于对程序作业的词法、语法和属性分析，抽取相关属性。 然后，总结各种度量技术的优势与不足。引入权重的概念，运用多种权重分析方 法，如单位加权法、加权平均法、等量加权法、多元回归法、矩阵运算法、层次 分析法、模糊综合评判法进行分析，建立多种代码相似度度量技术的综合分析模 型，扩展了程序作业系统对程序作业的测评方式，并提高了测评的准确性和全面 性。最后，在程序作业测评的实验分析中，抽样分析了众多作业系统中的模板程 序和学生程序，进行了系统测评和人工复核的方法比较分析，取得了较好的一致 性。 广东工业大学硕十学位论文 将系统测评模块应用到作业系统中，起到了辅助教师检测、评价和监督学生 学习的效果，为开展程序设计基础和数据结构等课程的教学改革、教学质量分析 等提供了新的分析工具，为改进教学质量作了进一步的支持。 关键词：程序测评；代码相似度；度量技术；权重 a b s t r a c t a b s t r a c t w i t ht h ei n c r e a s ei nc o m p u t e ra n dn e t w o r kt e c h n o l o g ya n dt h ep o p u l a r i t yo f c o m p u t e rm a c h i n et e s t ，o n l i n et e s t i n ga n do t h e rt e s t sa r ew i d e l yu s e di ns o c i a la n d n e t w o r k i n ge d u c a t i o n f o l l o w e db yc o m p u t e r - a i d e de v a l u a t i o n ( c o m p u t e ra s s i s t e d a s s e s s m e m ) t e c h n o l o g yh a sa l s ob e e nm o r ea t t e n t i o n t r a d i t i o n a lc o m p u t e r - a i d e d m e a s u r e m e n tt e c h n i q u eu s e df o rm o r es t a n d a r d i z e dt e s t sp r o v i d eo b j e c t i v ep r o b l e m s c o n v e n i e n ta n de f f i c i e n te v a l u a t i o n h o w e v e r , f l e x i b i l i t ya n dc r e a t i v i t yf o ras t r o n g s u b j e c t i v eq u e s t i o n , h o wj u d i c i o u so rn o t ，g i v e nh o wh i g ha n dl o wp o i n t s ，h a sb e e nt o r e l ym o r eo nm a n u a le v a l u a t i o n mt h e s i sh a da n a l y s ec o d es i m i l a r i t y sm e a s u r et e c h n o l o g y , m 妇t h e i m p r o v e m e n ti nt h ee x i s t i n gt e c h n o l o g y i nt h ee x i s t i n gp r o c e d u r ec o d es i m i l a r i t y s m e a s u r et e c h n o l o g y ，m a i n l yh a st h r e eb r o a dh e a d i n ge v a l u a t i o nt e c h n o l o g y , t h ef i r s t k i n di sb a s e do nt h ep r o c e d u r ea t t r i b u t et e c h n o l o g ym e a s u r e ，i n c l u d i n gi sa w a yf r o m , t h el a wo fc o s i n e su s i n gm i n k o w s k it oh ea w a yf r o ma n ds oo n ；t h es e c o n dk i n di s b a s e do nt h ep r o g r a ms t r u c t u r em e a s u r e ，i n c l u d i n gp r o c e d u r es l i c em e a s u r et e c h n o l o g y ， c i r c l eo r d e ro fc o m p l e x i t yn 舱a s u r et e c h n o l o g ya n ds oo n ；t h et h i r dk i n di sb a s e do n t h ec h a r a c t e rs t r i n gm a t c h i n gt e c h n o l o g ym e a s u r e ，i n c l u d i n gt h ed y n a m i cp r o g r a m m i n g l a w , b a s e do nt h el o n g e s tp u b l i cs u b s e ( u e l l c em e a s u r e ，b a s e do nt h el o n g e s tp u b l i c s u b s t r i n gm e a s u r e ，i sa w a yf r o mt h em e a s u r eb a s e do nt h ee d i t i o na n ds oo i le a c h m e a s u r em e t h o dh a si t sr e s p e c t i v eg o o da n db a dp o i n t s ，t h ei n d e p e n d e n te m p l o y m e n t e a c hk i n do fh l e a s u r et e c h n o l o g yh a si t s d e f i c i e n c y , m u s tt h e r e f o r e m a k et h e i m p r o v e m e mt ot h em e 嬲l l et e c h n o l o g y t h i sa r t i c l ef o c u s e so na n y v i e w cp r o g r a mj o bs y s t e ma s s e s s m e n ts t u d yo ft h e e x t e n s i o n f i r s to fa l l , o nt h ea n y v i e w ce x i s t i n gc o m p i l e re x t e n d e rp r o p e r t i e so ft h e e x t r a c t i o nm o d u l e ，b a s e do nt h ej o bo fl e x i c a l , s y n t a c t i ca n dp r o p e r t ya n a l y s i s ，e x t r a c t r e l e v a n tp r o p e r t i e s t h e n , s u m m a r i z et h ev a r i o u sm e a s u r e m e n tt e c h n o l o g ya d v a n t a g e s a n dd i s a d v a n t a g e s 1 1 1 ei n t r o d u c t i o no ft h ec o n c e p to fw e i g h t ，u s i n gv a r i o u sw e i g h t a n a l y s i sm e t h o d s ，s u c h a sf l a t w e i g h t i n g ，w e i g h t e da v e r a g e ，e q u a lw e i g h t i n g , m u l t i v a r i a t er e g r e s s i o n , m a t r i xm a t h , a n a l y t i c ，氏z 矾e s t a b l i s hm u l t i p l ec o d es i m i l a r i t y m e t r i co fc o m p r e h e n s i v ea n a l y s i sm o d e l , e x p a n d e dt h ej o bs y s t e mo np r o g r a m e v a l u a t i o no ft h ej o b a n dt oi m p r o v et h ea s s e s s m e n to ft h ea c c u r a c ya n d c o m p r e h e n s i v e n e s s f i n a l l y , i nt h ep r o c e s so fj o be v a l u a t i o no ft h ee x p e r i m e m ，t h e s a m p l ea n a l y z e di nt h et e m p l a t eo fm a n yo p e r a t i n gs y s t e mp r o c e s s e sa n dp r o c e d u r e s f o rs t u d e n t s ，c o n d u c t e das y s t e m a t i cr e v i e wo ft h em e t h o d so fe v a l u a t i o na n d c o m p a r a t i v ea n a l y s i so fa r t i f i c i a la n dm a d ei ng o o da g r e e m e n t 广东工业大学硕士学位论文 b ye x p e r i m e n t a la n a l y s i so f t h ep r o b l e ms y s t e mt od ot h et e m p l a t ep r o g r a ma n d s t u d e n tp r o g r a m , t h ef i r s td i s t i n g u i s h i n gm e t h o di nt h i sp a p e ri st h e nu s e dt oc o m p a r e m e t h o d so fm a n u a lr e v i e wt oo b t a i nab e t t e rc o n s i s t e n c y , i no r d e rt oa c h i e v ea s i m p l i f i e d m a n u a l i n s p e c t i o n w o r k l o a dp l a y e das e c o n d a r yt e a c h e rt e s t i l l g a n d m o n i t o r i n gs t u d e n tl e a m i n g r e s u l t s k e y w o r d s ：p r o g r a me v a l u a t i o n ，c o d es i m i l a r i t y ，t e a s u r e m e n tt e c h n o l o g y ，w e i g h t i v 目录 目录 摘j i j e i a b s t r a c t i i i c o n t e n t s i 第一章绪论。l 1 1 本文研究背景l 1 1 1 程序测试技术现状2 1 1 2 程序理解技术现状3 1 1 3 程序分析技术现状5 1 1 4 程序代码相似度技术现状6 1 2 本文研究内容7 1 2 1 基于程序模板的对比度量8 1 2 2 实验对象8 1 2 3 实验语言8 1 2 4 测评结果9 第二章程序作业测评处理过程1 0 2 1 程序预处理一l o 2 2 程序信息抽取1 1 2 3 程序结构规范化1 2 2 3 1 词法分析1 3 2 3 2 语法分析1 4 2 3 3 语义分析。1 4 2 3 4 结构等价转换15 2 4 程序测评1 7 第三章程序代码相似度算法及技术l8 3 1 相似度的定义与分类1 8 3 2 程序代码相似度技术。l9 3 2 l 基于程序属性技术的度量1 9 v 广东t 业大学硕士学位论文 3 2 2 基于程序结构技术的度量。2 l 3 2 3 基于字符串匹配技术的度量2 6 3 3 度量技术的改进3 2 3 3 1 度量技术特征分析3 2 3 3 2 权值的引入3 3 第四章程序代码相似度实现与分析3 9 4 1 代码相似度技术的实现3 9 4 1 1 基于属性统计的算法框架3 9 4 1 2 基于字符串匹配的算法框架3 9 4 1 3 基于圈复杂度的算法框架4 l 4 2 实验程序集的选择。4 l 4 3 实验程序及分析4 3 4 3 1 实验一4 3 4 3 2 实验二4 8 4 3 3 实验结果分析5 0 结论5 2 参考文献。5 4 攻读硕士学位期间发表的论文5 8 独创性声明5 9 致谢6 0 v 1 c o n t e n t s c o n t e n t s c h i n e s ea b s t r a c t i e n g l i s ha b s t r a c t i 】 c h a p t e r 1p r e f a c e 1 1 1b a c k g r o u n d 1 1 1 1p r o g r a ma n a l y s i sa n da s s e s s m e n t 2 1 1 2p r o g r a mu n d e r s t a n d i n g 3 1 1 3p r o g r a ma n a l y s i s 5 1 1 4p r o g r a ms i m i l a r i t y 6 1 2r e s e a r c hp o i n t s 7 1 2 1t e m p l a t e - b a s e dw o g r a me v a l u a t i o n 8 1 2 2t e s ts u b j e c t s 8 1 2 3t e s tl a n g u a g e 8 1 2 4r e s e a r c hr e s u l t 9 c h a p t e r2p r o c e d u r e sf o re v a l u a t i o np r o c e s s 1 0 2 1p r o g r a me v a l u a t i o np r o c e s s 1 0 2 2p r o g r a mi n f o r m a t i o ne x t r a c t i o n 11 2 3s t a n d a r d i z e dp r o g r a ms t r u c t u r e 1 2 2 3 1l e m c a la n a l y s i s 1 3 2 3 2s y n t a xa n a l y s i s 1 4 2 3 3s e m a n t i ca n a l y s i s 1 4 2 3 4e q u i v a l e mc o n s t r u c t i o n 15 2 4p r o g r a me v a l u a t i o nt e c h n i q u e s 1 7 c h a p t e r 3c o d es i m i l a r i t ya l g o r i t h ma n d t e c h n o l o g y 18 3 1d e f i n i t i o na n dc l a s s i f i c a t i o no fs i m i l a r i t y 18 3 2c o d es i m i l a r i t yt e c h n o l o g y 1 9 3 2 1a t t r i b u t e b a s e dp r o c e s sm e a s u r e m e n t t e c h n o l o g y 1 9 3 2 2t e c h n o l o g y - b a s e dm e a s u r eo f p r o g r a ms t r u c t u r e 2 1 v 广东t 业大学硕士学位论文 3 2 3m e t r i cb a s e do ns 1 矗n gm a t c h i n gt e c h n i q u e s 2 6 3 3i m p r o v e m e n to f m e a s u r e m e n tt e c h n i q u e s 3 2 3 3 1t e c h n i c a la n a l y s i sm e 娜e m e m 3 2 3 3 2 i h ei n t r o d u c t i o no f w e i g h t 3 3 c h a p t e r 4e x p e r i m e n ta n da n a l y s i s 3 9 4 1 n 】i 言c h o i c eo f e x p e r i m e n t a la s s e m b l y 3 9 4 1 1s t a t i s t i c so f t h ea l g o r i t h mf r a n 硷w o r kb a s e do na t t r i b u t e 。3 9 4 1 2a l g o r i t h mf r a m e w o r kb a s e do ns t r i n ga t t r i b u t e s 。3 9 4 1 3a l g o r i t h mb a s e do nc i r c l e sc o m p l i c a t e df r a m e 4 1 4 2e x p e r i m e n t a lp r o c e d u r ea n d a n a l y s i s 4 1 4 3e x p e r i m e m a lp m c e d u r ea n d a n a l y s i s 4 3 4 3 1e x p e r i m e n t1 4 3 4 3 2e x p e r i m e n t2 4 8 4 3 3e x p e r i m e n t a lr e s u l t s 5 0 c o n c l u s i 蚰! ；：! r e f e r e n c e s 5 4 p u b f i c a t i o n sd u r i n gm a s t e r ss t u d i e s 5 8 o r i g i n a lc r e a t i o nd e c l a r e 5 9 a c k n o w l e d g m e n t 6 0 v 第一章绪论 1 1 本文研究背景 第一章绪论 计算机辅助评价( c o m p u t e ra s s i s t e da s s e s s m e n t ，简称c a a ) 是指把计算机作 为工具或手段引入评价学习者的技能、知识和能力的过程，即计算机应用于评价 过程。与c a a 含义意思大致相同的术语还有：计算机辅助测试( c o p m u t e r - a s s i s t e d t e s t i n g ) 、计算机化评价( c o m p u t e r i z e da s s e s s m e n t ) 、基于计算机的评价 ( c o m p u t e r - b a s e da s s e s s ) 和基于计算机的测试( c o m p u t e r - b a s e dt e s t i n g ) ，他们都从 属于c a a 领域。 c a a 作为一种新的评价方式广为传播并被大众接受，有其自身的特点优势： 表1 - 1c a a 特点与优势 t a b l e1 - 1a d v a n t a g e so f c a a 角度特点与优势 测试者通过形成性评价，使测试者了解自己的学习进度； 通过总结性评价，使测试者可以进行分阶段的学习； 可以确认当前的教学方法是否有效。 教学c a a 使得大范围地区的评价更加迅速，节省时间耗费； 节省时间，使进行其它更有针对的评价活动成为可能； 通过形成性评价，可以了解测试者的学习进展情况； 在自适应测试( a d a p t i v et e s t i n g ) 过程中，发现学生整体 的弱点，从而调整教学方法。 管理减少了在监督管理、监考和评分上面花费的时间； 减少了在评分过程中因为人为因素而出现的错误； 使不同地点的学生同时进行评价时，节省了财力和人力； 进行无纸化考试，减少在印刷上面费用； 可以成功的对测试结果进行分级，并且自动的记录进被试 档案，数据库随机抽取题目，有效避免作弊。 因此，研究c a a 在教育评价中的应用具有重要意义：对于现代远程教育中 广东工业大学硕士学位论文 解决师生分离状态下的交互与反馈问题尤其具有应用价值；有利于教师监督检测 学生的学习过程，可以对学生进行与其能力相匹配的自适应测试；对于某些学科， 可实现测评与评价的自动化，这对于提供评测的质量、保证评测的一致性和公正 性，降低评测代价，都具有重要的意义；c a a 可以得到各种相关数据和自动生成 诊断分析报告，这对促进教育评价的量化研究，也具有极为深远的意义。 程序设计作为一种非标准化的能力，无论是在程序学习还是在c a a 程序测 评中都具有极大的灵活性，因此对程序设计的测评及程序设计的抄袭判别都具有 相当的难度，同时也具有很广泛的应用性。 软件版权问题一直以来都是一个难以解决的国际性问题，无论是软件版权的 检测研究还是软件版权保护的立法都相对滞后，对软件程序的分析研究，将可以 辅助解决软件版权纠纷问题，是一个应用性很强的技术和很有前途的领域。 本文针对本实验室研发的一款数据结构做题系统进行学生程序与模板程序 的相似度对比研究，作为一个突破口来阐述相关的技术研究。 1 1 1 程序测试技术现状 程序测试( p r o d a mt e s t i n g ) b 1 ，是指对一个完成了全部或部分功能、模块的计 算机程序在正式使用前的检测，以确保该程序能按预定的方式正确地运行。软件 测试是使用人工或者自动手段来运行或测试某个系统的过程，其目的在于检验它 是否满足规定的需求或弄清预期结果与实际结果之间的差别。它是帮助识别开发 完成( 中间或最终的版本) 的计算机软件( 整体或部分) 的正确度( c o r r e c t n o s s ) 、完 全度( c o m p l e t e n e s s ) 和质量( q u a l i t y ) 的软件过程；是s q a ( s o f t w a mq u a l i t ya s s u r a l l c e ) 的重要子域。 程序难以实现完全准确，测试是减少程序错误的重要手段，提高软件的可靠 性。 c m a r k e r h l 是一个c 语言的测评软件，它通过分析程序的结构和检查程序输 出的正确性，实现对程序的测评。但是它对不同的作业进行评分并不方便，而且 只能编译和执行一个c 文件，评分的规则也固定在c m a r k e r 里面，不能轻易修 改。 1 9 9 2 年，东南大学计算机科学与工程系研发的一款c 源程序分析及理解的辅 助工具c a a t 【5 1 ，其主要是通过对源程序的逐级抽象理解，对没有注释的反编 2 第一章绪论 译源代码进行添加注释、格式化显示，分析显示各类变量的使用情况，提供对宏、 变量、结构、联合等定义说明的查询显示，另外可输出模块调用关系及源程序中 的函数调用关系图。 1 9 9 9 年，新加坡国际大学计算机学院的s o n g w e nx u 等研制出了一个名为 s i p l e s - i i t s l 的系统用来分析学生程序，其主要采用了下列一些技术：采用了一种 名为面向对象程序依赖关系图( a o p d g ) 的结构；基于转化的程序标准化方法；语 义级程序比较；基于最大可能性的程序查错方法，查找其中错误并提供出错提示， 但是s i p l e s i i 系统只能分析内部函数( i n t r a - p r o c e d u r e ) ，不能对交互函数 ( i n t e r - p r o c e d u r e ) 和类的层次结构( c l a s sh i e r a r c h y ) 进行分析。 1 1 2 程序理解技术现状 程序理解( p r o g r a mc o m p r e h e n s i o n ) 1 7 是一个从计算机程序中获取知识的过程。 旨在理解一段已有的程序，通过不断地检查代码，逐步构建所需的理解。理解过 程中，不断地从中获取知识并提炼。程序理解是一个复杂的过程。理解过程中容 易出现信息丢失、前后不一致的情况，而造成理解困难。程序理解在提供给程序 初学者的程序教学中已成为广为讨论的话题h 1 。 在程序理解方面国外的研究可以追溯到1 9 7 0 年1 9 1 ，随着程序证明、程序维护 和人工智能的发展，人们开始涉足程序理解这一领域。在最近2 0 年来，程序理解 系统开始被人们提出，如支持逆向工程的程序理解工具r i g i 。r i g i 主要的工作在 于揭示系统的抽象信息和子系统层次的生成。这些层次结构可以在工具中从容地 进行浏览。 s h d m p i o 是一个通过嵌套的平面图形在单个窗体中展示一个软件系统的结 构的程序理解工具。与r j g i 相同，s h r i m p 生成的底层事物与源程序文本密切相 关。但不同之处在于，s h r i m p 是以超文本的形式呈现了源程序中函数调用、数 据类型引用和变量引用。 s n i f f + 是一个商业的软件开发环境，其提供项目管理、源程序浏览、交叉 引用和超强搜索的功能。一些相对独立的工具通过集成实现了这些功能。这些工 具都是工作在由s n i f f + 剖析源程序生成的符号表的基础之上。 1 9 9 8 年日本的h a r u k iu e n o 2 开发了基于知识生成方法的对p a s c a l 和c 语言理解的环境a l p u s 及a l p u si i ，建立了四个知识库：算法知识库、编程技 广东丁业大学硕士学位论文 巧知识库、变量知识库和b u g 库。通过知识库及其学习规则生成某些模板与标 准化后的学生程序进行比较，生成模板的种类包括标准模板、可接受模板以及 b u g 模板。通过依次比较这些模板，从而相应确定程序质量f l 引。 国内在程序理解方面的研究主要有北大青鸟工程的青鸟程序理解系统 j b p a s 。青鸟程序理解系统j b p a s ( j a d eb i r dp r o g r a ma n a l y s i ss y s t e m ) b j 是一个针 对c + + 语言的程序理解系统，由一个c h ：分析器前端和一组分析工具。其体系结 构如图所示： 图l - 1 j b p a s 体系结构图 f i g u r e1 - 1j b p a ss y s t e mc h a r t s 分析器前端采用e e r ( e n h a n c e de n t i t y - r e l a t i o n s h i p ) 为c + + 程序建立概念模 型，该模型较为全面，以适合多种程序信息需求。通过增量分析技术静态分析程 序源代码，按照概念模型抽取程序信息并将信息保存在增量数据库中。最后，启 动增量库链接器，将各个增量数据库链接成程序信息库。分析器前端由信息抽取 器和信息管理器组成。 分析工具包括： 1 程序理解工具( p r o g r a mu n d e r s t a n d i n gt 0 0 1 ) ：支持用户在程序理解过程中 采用的多种理解策略，用多层抽象视图表现程序，并方便程序理解过程中的用户 交互。 2 设计文档逆向生成工具( r e v e r s ed e s i g nd o c u m e n te n e r a t o r ) ：利用程序信息 库中的程序信息，自动生成程序的面向对象设计文档，以维护文档的一致性。 3 面向对象测试支持工具( o b j e c t - o r i e n t e dt e s t i n gs u p p o r t e r ) ：利用插装技术 跟踪程序的运行，以辅助测试用例的生成。 4 面向对象度量工具( o b j e c t - o r i e n t e dm e t r i c ss u p p o r t e r ) ：收集基于代码的度 4 第一章绪论 量数据并按特定的度量准则进行计算，以更好地反映程序的特性。 5 构件提取工具( c o m i 0 n c n te x t r a c t o r ) ：基于类和类树的信息，对类和类树 进行再工程以提取可复用的构件。 6 c 到c + + 转换工具( ct oc + + t r a n s l a t o r ) ：将c 程序转换为功能等价的c + + 程序，以充分利用非0 0 程序。 7 c + + 到o l e 转换工具( c + + t oo l et r a n s l a t o r ) ：辅助程序员将c + + 应用程序 转换为遵从o l e 接口标准的o l e 构件。 2 0 0 3 年哈尔滨工业大学提出一种程序理解方法，利用层次结构分析方法对程 序进行逆向分析得到一个程序的结构信息，将其用图形化方法表示出来，以便于 分析者理解程序的逻辑含义和程序结构间的逻辑关系。 1 1 3 程序分析技术现状 程序分析( p r o g r a ma n a l y s i s ) t s 】技术的研究主要针对不同的程序分析其不同的 属性，根据分析的结果为提高程序的性能，判定程序的正确性，对程序进行优化、 转换和理解等提供有用的信息。不同的程序分析技术将侧重于不同的方面： 从不同的角度分析程序，包括静态分析方法，动态分析方法等等； 针对程序的不同方面的进行分析，包括数据流分析、控制流分析等等； 针对不同类型的程序的分析技术，可分为顺序命令式程序的分析，对象式程 序的分析，并发程序的分析，针对不同需求的分析，如程序切片等。 所谓动态分析是利用调试器，如o l l y d b g 一步一步地单步执行软件。常见的 调试器有s o f l i c e ，o i i y d b g ( 简称o d ) 等。 程序静态分析是在不执行程序的情况下对其进行分析的技术，简称为静态分 析。而程序动态分析则是另外一种程序分析策略，需要实际执行程序。大多数情 况下，静态分析的输入都是源程序代码，只有极少数情况会使用目标代码。静态 分析这一术语一般用来形容自动化工具的分析，而人工分析则往往叫做程序理解。 静态分析越来越多地被应用到程序优化、软件错误检测等领域。c o v e n t yi n c 的软 件质量检测产品就是利用静态分析技术进行错误检测的成功代表。著名的静态分 析工具m e t a c o m p i l a t i o n ，由s t a n d f o r d 大学的d a w s o ne n g l e r 教授等研究开发，该 静态分析工具允许用户使用一种称作m e t a l 的状态机语言编写自定义的时序规则， 从而实现了静态分析工具的可扩展性“6 】。 5 广东工业大学硕士学位论文 数据流分析是一项编译时使用的技术，它能从程序代码中收集程序的语义信 息，并通过代数的方法在编译时确定变量的定义和使用。 程序的控制流图( c o n t r o lf l o wg r a p h , c f g ) ! ，是用在编译器中的一个抽象数 据结构。它是一个过程或程序的抽象表现，由编译器在内部维护，每个在图形中 的节点代表一个基本块，被用来确定对变量的一次赋值可能传播到程序中的哪些 部分。这些信息通常被编译器用来优化程序。 程序切片( p r o g r a ms l i c e ) 【t 。】是一种用于分解程序的程序分析技术，是通过对源 程序中每个兴趣点分别计算切片来达到对程序的分析和理解。程序切片有两个含 义，一种是把只与某个输出有关的语句和谓词构成的程序称为源程序的一种静态 切片；另一种是计算程序切片的过程。 程序评价是对一个程序进行分析，根据一定的标准对程序的分析结果进行评 分。 1 1 4 程序代码相似度技术现状 程序代码相似度度量技术主要应用在代码的剽窃检测上。判断一个程序是否 是从另一个程序复制而来，实质上是对这两个程序的相似度进行度量，根据度量 的结果给出一个相似度的数值表示，再由这个数值判断这两个程序之间是否存在 抄袭。 国外对程序代码相似度自动度量技术的研究始于2 0 世纪7 0 年代。1 9 7 7 年， 来自p u r d u e 大学的o t t e s s t e i n 首次将h a l s t e a d 的属性计数技术用于程序代码的抄 袭检测。这项技术用于检测非常小的程序时是有效的。因为