（计算机应用技术专业论文）基于转换的程序分析技术的研究与应用.pdf

摘要 摘要 程序的分析技术在许多领域有广泛的应用前景。例如，对学生程序的自动分 析评价；利用程序分析比较工具来辅助软件版权的分析鉴别。但是目前程序分析 评价技术主要停留在程序输出结果的比较，并不能发现那些通过编译但语义上有 问题的程序的错误；曾有个别学者尝试过在语义上分析评价程序，但是分析的目 标语言并不是国内外计算机教育普遍采用的编程语言。相关的研究，如程序理解、 程序度量和程序转换，虽然和程序分析评价的研究有一定的联系，但是国内外鲜 有将其综合起来用于程序分析评价的研究。 本文研究基于转换的程序分析技术及其在程序评价上的应用，并讨论了在其 他方面的应用前景。在研究编译器转换技术和代码优化相关技术的基础上，提出 了用于分析评价c 语言程序的a n a l y s e c 框架，并实现了其软件原型。a n a l y s e c 对程序分别进行结构相似性分析和语义分析评价，实现了程序度量及其可视化、 程序转换及其可视化、程序分析评价等功能。 在a n a l y s e c 中，使用a n t l r 构造一个以抽象语法树为中间代码的c 语言分 析器。在结构层次上，a n a l y s e c 基于程序的抽象语法树，应用传统的软件度量对 程序进行分析和可视化，并提出将数据结构的使用列为程序度量的元素之一，实 现程序的结构相似性分析。在语义层次上，使用在编译器当中用于代码优化的程 序依赖图作为程序的表现形式编译器使用代码优化相关技术的目的是使程序运 行得更加快，a n a l y s e c 使用该技术的目的是借助程序依赖图用于程序比较。应用 编译器的转换技术、内联扩展技术、前向替换等代码优化相关技术，对程序进行 保留语义的标准化转换、控制流分析和数据流分析，形成可以在语义上进行比较 的程序依赖图，最终通过程序划分、比较，实现程序的分析评价。 程序以源代码的形式提供给a n a l y s e c ，a n a l y s e c 在结构层次和语义层次对程 序进行分析，得出结构分析结果和语义分析结果，可以辅助教师评改编程作业， 同时也给予学生一定的上机辅导，提示程序可能出错的地方。a n a l y s e c 已经应用 于数据结构算法设计作业的分析与评价，能够分析评价部分学生作业。但是 a n a l y s e c 目前还是个软件原型，需要更多的努力使其完善，实际应用于程序的 自动分析评价和其他的应用领域。 关键词：程序分析；转换；比较；评价；可视化 广东t 业大学工学硕士学位论文 a bs t r a c t p r o g r a ma n a l y s i st e c h n o l o g yh a sab l i g h ta p p l i c a t i o nf u t u r ei nv a r i o u sf i e l d s , s u c h a s , a u t o m a t i ca n a l y s i sa n da s s e s s m e n tf o rs t u d e n tp r o g r a m m i n ge x e r c i s e s , a n dm a k i n g u 辩o f p r o g r a ma n a l y a i st o o lt oh e l pa n a l y s es o t l w 孤ec o p y r i g h t n o w a d a y s , t h ep r o g r a ma n a l y s i st e c h n o l o g ym a i n l yf o c u s e so nc o m p a r i s o no f p r o g r a mo u t p u t s i nt h i sw a y , t h eo n o r si nas u c c e s s f u l l yc o m p i l e dp r o g r a me a l m o tb e f o u n dt h r o u g hc o m p a r i s o l l t h e r ea r cs o l l 蟹s c h o l a r sw h oh a st r i e dt of i g u r e di to u tb y s e m a n t i cc o m p a r i s o n , b u tt h ep r o g r a m m i n gl a n g l l a g ct h e yh a v et r i e di sn o tt h ew i t h i n t h eo i l e sw i d e l yu s e dt h r o u g h o u tt h ew o r l d a l t h o u g ht h e r ea l es o r n er e l a t e d t e c h n o l o g i e s , s u e l a a sp r o g r a mc o r n p r e h e m i o n , s o f t w a r em e t r i c sa n dp r o g r a m t r a n s f o r m a t i o n , t h e r ei sl i t t l er e s e a r c ht h a ti n t e g r a t e sa n da p p l i e st h e s et e c h n o l o g i e st o p r o g r a m a n a l y s i sa n d a s s e s s m e n t i nt h i st h e s i s w ed or e s e a r c hi np r o g r a ma n a l y s i st e c h n o l o g ya n di t sa p p l i c a t i o n o np r o g r a ma s s e s s m e n t ，a n dd i s c u s st h ep r o s p e c to fo t h e ra p p l i c a t i o n s b a s e do i l t r a n s f o r m a t i o nt e c h n i q u e so f c o m p i l e r sa n dc o d eo p t i m i z a t i o nt e c h n o l o g y , w cp r o p o s e 4n 哪l i a m e w o r ka n a l y s e c 锄di m p l e m e n tt h ep r o t o t y p e a n a l y s e cf e a t u r e si n s o t t w a t em e t t l e s , s t r u c t u r a la n a l y s i s ，s e m a n t i ca n a l y s i sa n dv i s u a l i z a t i o n i na n a l y s e c w eu s ea n t l rt oc o r l s t n l c tacp s e r , w h i c hi sa b l et og e n e r a t e a b s t r a c ts y n t a xt r e e 船i n t e r m e d i a t el a 】1 9 u a g e a ts t r u c t u r a ll e v e l , b a s e do na b s t r a c t s y n t a xt r e e , a n a l y cl n a k c su o fs o f t w a r em e t r i c st oc o m p u t ea n dv i s u a l i z et h e l n c t l f i c $ i n f o r m a t i o no fp r o g r a m s w ep r o p o s et h a td a t as t r u c t u r eu s e di nap r o g r a m c a nb eak i n do fs o t t w a r ei i l “c $ t ol t l a l y z , eap r o g r a m a ts e m a n t i cl e v e l , p r o g r a m d e p e d e n e eg r a p ho r i g i n a l l yu s e di nc o d eo p t i m i z a t i o ni st h er e p r e s e n t a t i o nf o r mo f a p r o g r a m w ea p p l yt r a n s f o r m a t i o nt e c h n o l o g yo fc o m p i l e r sa n dc o d eo p t i m i z a t i o n t e c h n o l o g yt oa c h i e v es e m a n t i c a l l yp r e s e r v i n gu a m f o r m a t i o n , c o n t r o lf l o wa n a l y s i s a n dd a t af l o wa n a l y s i s , f o r m i n gp r o g r a mo e r 删l e n e eg r a p h , af o r mt h a tc a nb e c o n l p a t c da ts e m a n t i cl e v e l f i n a l l y , t h r o u g hp a r t i t i o na n dc o m p a s s i o no f t h ep r o g r a m d 辨n d c n c cg r a p h , a l la s s e s s m e n tr e p o r ti sg i v e n , i d e m i 黟i l l gt h es e m a n t i cd i f f e r e n c e s o f t w op r o g r a m s s o u r c ec o d ei sp r o v i d e dt oa n a l y s e ( ；t op e r f o r ma s s e s s m e n t a n a l y s e ca n a l y s e s p r o g r a m sa ts t r u e t u r a la n ds e m a n t i cl e v e lg e n e r a t i n ga n a l y s i sr e s u l t s i t 锄f a c i l i t e a b s t r a c t t e a c h e r si na s s e s s i n gp r o g r a m m m ge x e r c i s e s , a n dg i v es t u d e n t sa s s i s t a n c ew h e nt h e y f i n dd i f f i c u l ti n 锄i i l ge l t o r s t h ep r o t y p eo f a n a l y s e cc a nf l o wa n a l y s es o m cs p e c i f i c e x e r c i s e so fd a t as t r u c t u r ec o u r s e b u ti ts t i l lh a sal o n gw a yt og ob e f o r ei tc 蛆b e p r a c t i c a l l yu s e di na u t o m a t i cp r o g r a ma s s e s s m e n ta n do t h e rf i e l d si nt h er e a lw o r l d k e y w o r d s ：p r o g r a ma n a l y s i s , t r a n s f o r m a t i o n , c o m p a r i s o n , a s s e s s m e n t , v i s u a l i z a t i o n i l l 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 论文作者签字 指导教师签字 ：新强、 ， 脚 0 2 0 0 7 年5 月l o 日 第一章绪论 1 1 本文研究背景 第一章绪论 程序的分析技术在教育和信息产业等领域都有着广泛的应用前景。 1 教育领域对学生程序的自动分析评价有着迫切的需求。 经过多年的扩大招生，我国的高等教育的规模从1 9 9 8 年的6 4 3 万人增加到 2 0 0 4 年的2 0 0 0 多万人，净增长1 4 0 0 万人；而全国普通高等学校教职工仅从1 9 9 8 年的1 0 2 9 6 万人增加到2 0 0 4 年的1 6 1 0 7 万人，净增长5 8 万人四，其中计算机相 关专业的学生数量的增长占了相当大一部分，而教职工的增长速度远远落后于高 等教育扩招的速度。 以广东工业大学计算机学院为例，本科全日制学生人数从1 9 9 8 年的几百人增 加到现在的近4 0 0 0 人，而教职工增长远远没跟上这个增长速度，扩招日渐暴露出 问题。对于计算机专业的学生，动手能力十分重要，上机编程练习应当是学习的 一个重要环节，学生需要得到上机编程方面的足够指导。 虽然开发了数据结构算法设计可视化作业系统，学生可以通过该系统完成编 程作业，提高了教学质量，但是学生的编程指导仍依赖于教师。尤其是初学编程 的学生，对于编译通过但结果错误的程序一筹莫展，特别需要指导。而由于条件 限制，教师不可能实现对学生的一对一的辅导，因而程序的自动分析、评价对于 辅导学生、实现程序作业系统的作业、辅导一体化是十分必要的如果有了程序 的自动分析评价，学生在上机编程遇到问题时，可以首先通过系统的分析评价信 息尝试解决问题。这样不仅可以提高学生学习编程的效率和积极性，而且可以大 大减轻教师的负担。在另一方面，学生程序作业的抄袭问题随着网络的发展而日 益严重。在上机课上，一旦有一个同学完成了上机作业，很快全班的同学也都完 成了在完成的上机作业里面，很大一部分是抄袭的。防止抄袭的有力手段之一 是研发检测抄袭的工具，程序分析技术的研究为抄袭检测研究打下了基础。 2 在信息产业领域，软件的版权问题不断浮现，版权纠纷日益增多，其中国 内典型的软件版权纠纷案例有1 9 9 7 年8 月的香港p a c i f i cu n i d a t al i m i t e d 公司和 广东工业大学t 学硕士学位论文 北京京延电子有限公司诉广州雅芳有限公司的计算机软件著作权侵权纠纷案， 2 0 0 3 年的姚毅与北京大恒医疗设备有限公司的计算机软件著作权权属纠纷案， 2 0 0 4 年的“a u t o d e s k 软件”著作权侵权纠纷案，2 0 0 5 年7 月的友泰软件版权纠 纷案。目前从事计算机软件开发的人员流动性大，是造成软件版权纠纷的主要原 因之一。以2 0 0 5 年7 月的友泰软件版权纠纷案为例，原友泰软件公司的5 名核心 开发人员离职，到相同领域的另一公司从事类似软件的开发。这必然引起友泰软 件版权的纠纷。 然而，怎样判定软件是否侵权，仍然是一个很模糊的概念。在软件版权是否 侵权的判定中，美国法院通常会采取抽象，过滤和比较的“三步判定法”第一步 对计算机程序进行抽象，就是将指控他人侵权的原告程序分解为各级构成层次， 从代码、子模块、模块直到最高层次的功能设计，对程序分层次逐级抽象， 将思想抽象出来。随着抽象层次的上升，被抽象出来的思想就越多，而剩下的“表 现”就越少。第二步过滤，即将抽象掉思想的各层次的表现，逐层次进行“过滤” 根据硬件环境，兼容性条件、效率因素、公有领域因素等外部因素过滤出不受保 护的内容。第三步比较，把过滤后剩余的部分与被指控侵权的程序在逐个抽象层 次进行比较，以确定被告是否复制了过滤后剩下的“表现”。若确有复制，还需进 一步评价被复制部分在程序中所占的重要性。而且，侵权判定很大程度上依靠有 经验的软件研究人员人手完成。 在国内，无论是软件版权保护的立法还是软件版权检测的研究都相对滞后， 对软件分析技术进行研究并应用到辅助解决软件版权纠纷问题，是一个新兴的、 很有前途的领域。 1 1 1 程序分析评价技术现状 程序评价是对一个程序进行分析，根据一定的标准对程序程序的分析结果进 行评分。 1 9 9 2 年，东南大学计算机科学与工程系研制了一种c 源程序分析及理解的辅 助工具c a a t “，其主要通过对源程序的逐级抽象理解对没有注释的反编译 源代码进行添加注释、格式化显示，分析显示各类变量的使用情况，提供对宏、 变量、结构、联合等定义说明的查询显示，另外可输出模块调用关系及源程序中 的函数调用关系图。 第一章绪论 我院正在使用的数据结构作业系统侧重于提供一个程序作业可视化运行和调 试的环境。该系统内嵌了一个编译器，通过检查输出结果来判断程序的正误，但 并未在程序分析、语义查错方面做工作。 我们工作室0 5 届硕士樊敏在学位论文中，基于程序表达，程序转换，和程 序比较等技术，对程序作业自动测评进行了研究，提出了程序对等结构，等价结 构和程序结构规范化的概念，以及确定对等结构的方法和比较确定等价结构的规 则。但是整个系统的设计很大程度上处于理论阶段，尚需理论和实验验证。设计 的测评目标语言是c 语言的子集，没有指针，不允许递归，属于内部函数的测评， 且只有基本类型和基本运算，实际应用价值有待提高。 c - m a r k e r 啪是一个c 语言的测评软件，它通过分析程序的结构和检查程序输 出的正确性，实现对程序的测评。但是它对不同的作业进行评分十分不方便，而 且只能编译和执行一个c 文件，评分的规则也固定在c m a r k e r 里面，不能轻易 修改。 g e n e r ka u t o m a t e dm a r k i n ge n v i r o n m e n t ，简称g a m e ”，是一个通用的j a v a 程序的测评工具。它针对c m a r k e r 进行了改进，可以动态地对不同类型、不同语 言的程序作业进行测评，而且还可以方便地修改评分策略。但是g a m e 是建立在 比较程序输出的基础上的，对于编译未通过的程序则无法分析和评分，也不能为 编译通过但语义错误的程序给出修改提示；学生也有可能通过虚假输出来作弊。 类似地，a no n l i n ep r o g r a m m i n ga s s e s s m e n tt o o l t s 3 , o n l i n ej u d g e 旧，a s a p ” 也是通过匹配程序的输出结果判断程序的正误，无法定位程序语义上的错误，缺 乏分析、查错等辅导学生的功能。 国立新加坡大学计算机学院的s o n g w e nx u 等研制出s i p l e s - i i 限”系统来 分析学生程序，查找其中错误并提供出错提示，从而提供一个更为智能化的编程 学习环境。其主要采用了下列一些新技术：采用了一种名为面向对象程序依赖关 系图( a o p d g ) 的结构；基于转换的程序标准化方法；语义级的程序比较；基于 最大可能性的程序查错方法。 广东t 业大学一【学硕士学位论文 图1 1s i p l e s i i 系统的分析流程嘲 f i g u r e1 - lp r o c e d u r eo f d i a g n o s i si ns i p l e s - i is y s t e m 但是s i p l e s i i 系统是针对s m a l l t a l k 语言的，而s m a l l t a l k 在我国并不普及， 而且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 ) 进行分析。 i - i r i s t o v a 等人“”联系了5 8 所u sn e w s 中列举的大学的计算机科学教授和 a c m 的s i g c s e 专家，收集了一系列j a v a 编程的常见错误( 分类成语法错误、 语义错误、逻辑错误) ，开发了e x p r e 船o 它具有较一般编译器高的分析查错功能， 能为产生有用的错误信息并提供修改代码的建议。但是该系统的语义分析查错能 力不强，只能分析出少量语义错误，例如不使用“”号的类成员函数调用。 1 1 2 程序理解技术现状 程序理解是一个从计算机程序中获取知识的过程。旨在理解一段已有的程序， 通过不断地检查代码，逐步构建所需的理解。理解过程中，不断地从中获取知识 并提炼。程序理解是一个复杂的过程。理解过程中容易出现信息丢失、前后不一 致的情况，而造成理解困难。程序理解在提供给程序初学者的程序教学中已是广 为讨论的话题删。 在程序理解方面国外的研究可以追溯到1 9 7 0 年，随着程序证明、程序维护和 人工智能的发展，人们开始涉足程序理解这一领域。在最近2 0 年来，程序理解系 统开始被人们提出，如支持逆向工程的程序理解工具r i g i c 3 。4 明，它的工作由两部 分组成：1 剖析阶段；2 发掘阶段。剖析阶段主要的工作是：剖析源程序，用自带 的图像编辑器生成一个能够操作和浏览的资源流平面图。随后的发掘阶段是一个 第一章绪论 半自动化阶段，涉及了一些模式识别技巧和领域知识。此阶段中逆向工程人员通 过剖析阶段建立的平面图，确定源程序中含有的子系统，构造出有意义的高层抽 象模型。这些子系统能够递归地收缩和打开，形成一个层次结构。r i g i 能够根据 用户关心的类型过滤掉不需要的信息，方便用户的浏览。不过，r i g i 不支持直接 地搜索源代码文本。总之，r i g i 主要的工作放在揭示系统的抽象信息和子系统层 次的生成。这些层次结构为在工具中从容地浏览起到了重要的作用。 s n i f f + o ”1 是一个商业的软件开发环境，它提供项目管理、源程序浏览、交 叉引用和超强搜索的功能。一些相对独立的工具通过集成实现了这些功能。这些 工具都是工作在由s n i f f + 剖析源程序生成的符号表基础上。项目管理窗口列出了 源程序的头文件和实现文件。符号浏览器显示了函数、常量、宏和变量等符号。 这些符号可以自定义显示条件。源代码编辑器用语法规则高亮显示了源代码文本 搜索后的结果。 1 9 9 8 年日本的h a r u k iu e n o 开发了基于知识生成方法的对p a s c a l 和c 语言理解的环境a l p u s 及a l p u si i ，建立了四个知识库：算法知识库、编程技 巧知识库、变量知识库和b u g 库。通过知识库及其学习规则生成某些模板与标 准化后的学生程序进行比较，生成模板的种类包括标准模板、可接受模板以及 b u g 模板。需要依次与这些模板进行比照，从而相应确定程序质量“”。 国内在程序理解方面的研究主要有北大青鸟工程的青鸟程序理解系统 j b p a s 。青鸟程序理解系统j b p a s ( j a d eb i r dp r o g r a m a n a l y s i ss y s t e m ) 是一 个针对c h 语言的程序理解系统，由一个晰析器前端和一组分析工具组成， 分析器前端采用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 + + 程序建立概念模型， 该模型较为全面，以适合多种程序信息需求。通过增量分析技术静态分析程序员 代码，按照概念模型抽取程序信息并将信息保存在增量数据库中。最后，启动增 量库链接器，将各个增量数据库链接成程序信息库溉删。 2 0 0 3 年哈尔滨工业大学提出一种程序理解方法嘲，利用层次结构分析方法通 过对程序的逆向分析可以得到一个程序的结构信息，并将其最后用图形化方法表 示出来，以便于分析者理解程序的逻辑含义和程序结构问的逻辑关系。这篇论文 主要侧重于程序结构的理解，对于分析大型软件结构有很大帮助，但是不能做到 较精确地查看程序正确性。 广东工业大学t 学硕士学位论文 1 - 1 3 程序度量技术现状 获得高质量的软件是软件工程的目标之一。低劣质量的软件，除了影响软件 的使用外，还会导致软件维护的成本成倍增加，甚至会给用户带来巨大的损失。 因此，全面综合地评价软件质量必须要对软件实施度量。 i e e e 在“s t a n d a r df o rs o t t w a r e q u a l i t y m e t r i c s m e t h o d o l o g y , i e e e s t d 1 0 6 1 1 9 9 2 。1 9 9 3 ”中对度量( m e t r i c s ) 下了定义：“度量是一个函数，它的输入 是软件数据，输出是单一的数值，能用以解释软件所具有的一个给定属性对软件 质量影响的程度。”嘲 近年来面向对象的软件质量度量的研究正日益受到广大科研工作者的重视， 研究成果不断涌现。这一切表明面向对象软件度量的领域正处在一个不断变化发 展的过程中。目前己提出的面向对象软件度量己有几十种，并有一些成熟的产品 吼剐，例如： 1 基于c h 上的度量工具o om e tt o o l , o o s q a ，o b j e c td e t a i l 等。 2 基于s m a l l t a l k 上的度量工具o o m , o m d 等。 其中o o m 是由日本s r a 公司开发的。它主要支持以下几类度量( m e t r i c s ) ： 1 ) c & k 提出的六个度量( m e t r i c s ) ： w m c ，d i t , n o c ，c b o , r f c ，l c o m 2 1b a s i cm e t r i c s 。即七个最基本的度量( m e t r i c s ) ： 乱l o c ：类中行代码的数量； b n o a ：属性的数量； c n c v ：一个类中类变量的个数； d n i v ：一个类中i n s t a n c e 变量的个数； c n o m ：一个类中方法的数量； n i m ：一个类中i n s t a n c e 方法数目； g n c m - 一个类中类方法的数量。 o o m 基于v i s u a lw o r k ss m a u t a l k 环境，利用上述度量( m e a i c s ) 对软件质量可 进行较合理的评估。 美国德州理工大学的s u s a n 八m e n g e l 教授“”描述了一个使用商用静态分析 工具v e r i l o gl o g i s c o p e 对学生程序进行静态分析的实验，通过对程序度量 6 第一章绪论 ( m e t r i c s ) 的分析，包括一致性( 程序的大小、复杂度) 、函数的数量、语句的数 量、注释、调用图的质量等，从而判断程序的质量。这个实验的目的是探讨这种 方法是否适用于程序质量的自动评价，但是这种方法的有效性有待提高“8 。 1 1 4 程序转换技术现状 在编译器中，从源代码翻译成中间代码、抽象语法树，到代码优化中的控制 流分析、循环优化，普遍使用了程序转换技术。这里所指的程序变换，都是以不 改变程序的语义为前提的，称为保留语义的程序变换嘲。 在软件工程当中，按照不同的需要存在这样各种各样的程序转换。 1 ) 将一种语言程序转换成另一种语言程序，特别是将低级语言程序转换成为 高级语言程序，以帮助程序理解，解决遗产代码的问题。 2 0 0 3 年中国科学院计算技术研究所对c o b o l 到j a v a 源代码翻译进行了相关研 究，开发了c o b o l 2 j a v a 转换器嘲。它首先对c o b o l 和j a v a 语台之间的不同点进行 了对比，然后分析了几种主要的遗产代码迁移策略。基于以上的分析，此文设计 和实现了一个将c o b o l 源代码翻译到j a v a 源代码的系统c o t a 翻译系统，解决 了c o b o l 2 j a v a 实践中遇到的条件名变量转换、数据对象模型映射、控制流重构、 动态调用以及文件和数据库访问等一系列关键问题。在这一过程中，此文深入研 究了源代码翻译中的数据类型转换问题，控制流结构化问题和用户界面迁移问题， 针对这三个问题分别提出并实现了自动化的功能等价的转换方法可以有效的将遗 产代码迁移到目标平台 2 ) 将一种语言转换成该语言的子集，以增强该语言的安全性、稳定性 2 0 0 2 年美国加州大学伯克利分校的g e o r g ecn e c u l a 等人，在研发了c i n t e m e 甜i a t el a n g u a g e ( c i l ) “”c i l 通过源代码到源代码的转换，将c 语言程序转 换成一种比抽象语法树低级、比三地址码高级的很容易分析的中间代码。这种转 换生成的代码跟原来的c 语言程序很相像，相当于一种缩小了的c 语言。应用转 换生成的中间代码不仅能够帮助分析一个系统，而且能够在系统运行时进行检查， 保证类型的安全。 3 ) 在程序当中插入安全检查代码，转换之后的程序有更好的安全性。 2 0 0 6 年美国德州大学达拉斯分校的k e v h lwh a m l e n 教授，对n e t 平台的中 间代码c o m m o mi n t e m e d i a t ei 舢訇培g n e tc i l ) 进行了深入研究，提出一种称为 7 广东工业大学1 = 学硕十学位论文 m o b i l e 的n e tc i l 的扩展啷“1 。m o b i l e 在每个可能出现类型、访问等安全问题的 地方，插入按照给定的安全方针编写的c i l 代码，即对原来的c i l 代码进行重写， 使程序具有更好的安全性。 1 2 本文研究要点 本文主要研究基于转换的程序分析技术及其在学生程序分析评价上的应用， 并对该技术在软件版权分析鉴别等方面的应用进行讨论。 尽管不少学者在程序分析评价等相关技术方面做了一些工作，但是大多使用 比较实际输出与标准输出的方法来判断程序的正误，这种方法并不完善：1 ) 程序 编写人可以通过模仿标准输出试图通过测试；2 ) 一些程序虽然可以通过编译，但 是输出结果是错误的，这些错误并不能在程序中检查出来，更不用说把错误信息 反馈给程序编写者了，而这些提示信息在计算机辅助教学中是极其重要的。 国立新加坡大学的s i p l e s - i i 系统阻”对在语义层次上分析评价程序进行了尝 试，而且有一定成效。但是s i p l e s i i 系统是针对s m a l l t a l k 语言的，而s m a l l t a l k 语言的教学在我国的大学教育中并不普及，而且s i p l e s - i i 系统只能分析内部函 数( i n t r a - p m c e d u r e ) ，不能对交互函数( i n t e r - p r o c e d u r e ) 和类的层次结构( c l a s s h i e r a r c h y ) 进行分析。 程序度量已经在工程上得以广泛应用于工程量的估计、程序质量等，但是很 少用于程序分析评价。美国德州理工大学的s u s a n a m e n g e l 教授使用程序度量在 程序分析评价方面的研究只是一个尝试，实用性有待提高 将编译器的代码优化相关技术应用到程序转换分析，将程序转换到一个能够 比较的形式，从而实现程序的比较、评价。应用此方法，可以将模板程序和学生 程序进行转换、分析比较他们在结构上和语义上的差别，从而实现对学生程序的 自动评价。 1 2 1 词法和语法分析器的构造 a n t l r 嗍1 开发包的例子程序已经包含了j a v a 语言的a n t l r 元语言，可以 容易地使用a n t l r 生成j a v a 语言的分析器；然而a n t l r 开发包中并没有c 语言的a n t l r 元语言，只有一个称为t m y c 的a n t l r 元语言。t i n y c 只是c 语言的一个子集，仅包含关键字h a t 、c h a r 、i f , e l s e 、w h i l e ，仅能处理单个函数内 第一章绪论 部的语句。 因此，我们需要扩充t m y c ，使其能够分析绝大部分的c 语言程序；同时构 造抽象语法树，为程序的分析做铺垫。 1 2 2 程序度量 m c c a b e l 9 7 6 年提出了环形复杂度响( c y c l o n t a t i cc o m p l e x i t y ) 理论，该理论以 图论为基础，通过分析程序的控制流图来获得程序的复杂度，为度量程序逻辑复 杂性提供了一种很好的方法。这种度量可以统计顺序、选择、循环等逻辑判断的 复杂性，但是并没有分别区分各种逻辑判别。在程序的比较评价中，有针对性的 指出各种逻辑判断的度量，是很有必要的。针对程序比较评价中的需要，本文选 择条件选择( 的、循环和分支( s w i t c h ) 为度量的对象。 在研究传统程序度量的基础上，本文的重点是添加程序调用图的可视化对比 以及对程序中所使用的数据结构的度量。 在传统的程序度量中，传统程序度量中n o m 仅仅统计函数的数量，不能反 映函数调用的具体情况，如函数调用链和递归。本文着重研究函数调用的度量及 其可视化。 传统程序度量中n c v 统计的是变量的个数，而没有区分变量的类型，尤其 是数据结构的类型。在一个程序中，数据结构的使用很大程度上影响了程序的设 计思路和质量。因此，数据结构的度量对于软件度量是一个很重要的方面，而据 我所知，数据结构的度量在程序度量中并没有深入研究和使用。 1 2 3 交互函数到内部函数的转换 程序可以有很多小的函数，并且需要在程序中从一个地方到另一个地方不断 地传递这些小函数。然而，这些小函数正是引起程序多样性的原因之一。例如， 一个程序只有一个函数，而另一个程序包含有3 个小函数，但实现的思路都是一 样的。把后者转换成只用一个函数实现，是实现程序的比较分析的有效途径。 编译器中有一种很重要的优化技术一函数的内联扩展：用函数体的副本代 替函数调用。a n a l y s e c 设计借鉴编译器的内联扩展技术，根据程序分析评价的需 要，实现对交互函数到内部函数的转换。 1 2 4 内部函数分析 9 广东1 = 业大学t 学硕十学位论文 内部函数分析主要研究如何将编译器的中间代码表示、代码优化相关技术应 用到程序的分析评价。内容包括程序的基本转换、程序依赖图的生成以及程序的 高级转换。内部函数分析的结果是得到能够用来程序比较的程序表达形式程 序依赖图。 1 2 5 程序的比较和评价 在研究现有程序划分算法的基础上，设计适合于本课题使用的程序依赖图的 程序划分算法，该算法将两个程序的程序依赖图划分至一个个相对应的结点。并 提出针对c 语言的程序依赖图的比较、评价算法。 1 3 课题目标 通过对以上相关技术的研究，计划设计并实现c 语言程序分析评价的工具 a n a l y s e c ，对数据结构相关的算法设计作业进行自动分析和评价。a n a l y s e c 对程 序分别进行结构相似性分析和语义分析评价，实现了程序度量及其可视化、程序 转换及其可视化、程序分析评价等功能。课题的目标为“基于转换的程序分析技 术在程序比较评价方面的研究与应用”。 1 4 内容组织 论文的内容组织如下： 第一章介绍相关理论和技术的背景、现状以及研究要点； 第二章论述a n a l y s e c 的系统框架； 第三章论述c 语言分析器的构造； 第四章论述使用程序度量等技术在结构层次的程序分析； 第五章论述使用各种转换技术在语义层次的程序分析； 第六章论述程序的比较和评价； 第七章列出了运行示例并对应用前景进行了讨论； 最后总结了本课题的工作，并对后续工作进行了讨论。 第二章a n a l y s e c 系统框架 第二章a n a l y s e c 系统框架 a n a l y s e c 是本课题针对c 语言提出的程序分析系统。根据课题的目标，首先 定义c 语言程序分析系统a n a l y s e c 的系统功能。a n a l y t i c 主要从两个层次对程 序进行分析：结构层次和语义层次。结构层次的分析主要从程序度量的角度进行， 通过分析程序的控制结构、函数调用和使用的数据结构，检查程序之间的结构相 似性。语义层次的分析主要使用编译器相关的技术，对程序进行保留语义的标准 化转换，得到可以进行比较的程序语义表现形式程序依赖图，并对程序进行 分析评价。 2 1a n a l y s e c 的系统框架 根据课题的目标，可以定义a n a l y s e c 的系统框架。系统框架如图2 - l 所示： 学生程序 模板程序 抽象语法树抽象语法树 分析结果评价结果分析结果 图2 - 1a n a l y s e c 的系统框架 f i g u r e2 - 1a n a l y s e cf r a m e w o r k l l 广东工业大学- 学硕士学位论文 在a n a l y s e c 框架中，学生程序和模板程序首先通过利用a n t l r 生成的c 语 言分析器生成抽象语法树。学生程序和模板程序的抽象语法树是程序转换的基础。 在结构层次的分析中，根据抽象语法树对学生程序和模板程序分别计算软件度量 信息，并将各自的函数调用可视化。在语义层次的分析中，学生程序和模板程序 分别被分析并转换成程序依赖图。根据程序依赖图，两个程序相互进行比较，进 而发现相互之间的差异，并向教师和学生提供程序分析评价的结果和修改提示。 2 2 开发a n a l y s e c 使用的主要工具 分析器主要有以下两种开发方式： ( 1 ) 使用传统的方法依次编写词法分析器、语法分析器、语义分析器、中间 代码生成器等各个程序。 使用传统的方法的优点在于可以掌握核心代码的编写。使编译器独立于编译 器开发工具：缺点在于工作量太大。本文的重点不在于分析器的开发，而是在于 中间代码的转换。 ( 2 ) 使用成熟的编译器开发工具 例如由贝尔实验室开发的语法分析器的自动生成工具y a c c ，词法分析器的 自动生成工具s c a n g e n ，由美国a r c h e l o n 公司开发的可重定位编译器开发工具一 r e t a r g e t a b l ec o m p i l e rd e v e l o p m e n tt o o l s 。应用这些工具，不用亲自编写词法分析、 语法分析等程序，只需要按照要求将描述语言语法和机器指令的文件表述清楚即 可自动生成所需的编译器。 a n a l y s e c 课题的研究重点在于程序的转换、分析与评价，对c 语言的分析是 本课题的基础，但不是重点。因此，我们引入a n t l r 作为c 语言分析器的生成 工具。 2 2 1a n n ，r 的引入 a n t l r t “1 ( 另一个语言识别工具，a n o t h e rt o o lf o rl a n g u a g er e c o g n i t i o n ) 是一 个用来生成用户自定义语法一使用a n t l r 语法定义规范( 类似于y a c c 和 b e n f 规范) 或特殊的a s t ( 抽象语法树a b s t r a c ts y n t a x t r e e ) 语法的分析器和翻译 器的工具。a n t l r 会创建词法器，语法分析器和抽象语法树。它不只是一个语 法定义规范，它所提供的工具集，允许用户使用a n t l r 定义语法，并自动生成此语 1 2 第二章a n a l y s e c 系统框架 法的分析器，从而实现该语法，并且可以以多种语法方式如j a v a 、c + + 、s a t h e r 的方式实现。a n t l r 实现了p r e d l l ( k ) 分析策略，并提供了一个任意长度的前 向搜索，以反模糊( 去除二义性) 。 使用a n t l r ，我们可以定义词法规则，这样a n t l r 会根据这些规则自动将 字符流分割成一个个的t o k e n 。同时可以定义语法规则，a n t l r 根据它来识别 t o k e n 流。然后a n t l r 会生成一个i , e x e r 和r e c o g n i z e r ，这们可以直接使用这两 个生成的代码来分析我们的目标源代码，并将它们转换成其它语言或a s t 。 a n t l r 还具有非常强的可扩展性，并且已经有很多基于a n t l r 的应用了。 跟其他编译器生成工具相比，a n t l r 有以下优点： ( 1 ) 生成的j a v a 语言编写的分析器，使用方便，可以方便地跟其他类库( 如 数据结构类库j d s l ，可视化类库j a v a 2