形式化事实提取及其在逆向工程中的应用

理论计算机科学电子札记94（2004）93-102www.elsevier.com/locate/entcs形式化事实提取袁林1滑铁卢大学计算机科学学院地址：200 University AvenueWest Waterloo，ON N2L 3G1，CanadaRichard C. 霍尔特2号滑铁卢大学计算机科学学院地址：200 University AvenueWest Waterloo，ON N2L 3G1，Canada摘要逆向工程通常使用事实提取将源程序转换为事实库。这些事实库又被用来确定程序的特定视图或方面，例如其架构或异常结构。事实提取通常是以一种特别的方式定义的，这种方式往往是不完整或不一致的。本文的立场，事实提取的形式规格说明是有益的逆向工程社区。对于使用、编写或验证事实提取器的人来说，正式规范可以作为一个明确可靠的标准我们解释了如何提取的事实的正式规范可以从源语言的语法，这样的方式，代码和其相应的提取的事实之间的关系是明确的。为了支持我们的立场，我们报告我们的经验，正式版本的Datrix模式。保留字：模式，形式化，事实抽取，软件体系结构1介绍事实提取是一个解析源代码并生成存储有关信息的事实库的过程。建立准确可靠的事实基础1电子邮件：y3lin@uwaterloo.ca2电子邮件：holt@uwaterloo.ca1571-0661 © 2004由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2004.01.00194Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-因为逆向工程和程序理解工具通常依赖于事实库来分析软件。这对于通过事实库交换信息的软件工具也很重要。然而，编写一个事实提取器，一个从源代码中提取事实的程序，通常是一个复杂的工程问题，特别是对于像C++这样的语言，由于语言的复杂性。相关研究表明，事实提取器通常不同意并在同一源程序上发出不同的事实[1][12][8]。这往往会破坏用户对程序的理解，并降低他们对提取器的信心。事实提取器之间的这种不一致性也导致逆向工程工具之间交换信息的麻烦根据[8]，模式是对数据形式的描述，用一组具有规定形式的属性和关系的实体来表示的实例数据。事实库有一些特定的模式，例如Datrix和Columbus[2，9]。这些模式描述了事实库的形式，并将事实库中的实体与源语言联系起来。它们也是如何建立事实库的指导方针。在本文中，我们将专注于输入源代码并根据上下文无关语法解析它的事实提取器。并非所有的事实提取者都采用这种方法。例如，有些使用词法、非语法方法，有些分析目标代码。然而，我们所关注的方法是常用的。从源代码中提取的事实的模式规范通常是非正式和不完整的。由于这些非正式规范中的模糊性，事实提取器的每个开发人员都必须自己决定详细的形式事实数据库中的错误和不一致性。本文描述了我们的方法，形式化的事实提取，并创建一个完整的，一致的和可理解的基础事实提取。我们的事实提取的形式化包括三个部分：1) 源语言2) factbase语法和3) 从源语言映射到事实库的一系列步骤。使用这种方法编写的规范是合理的简短和易于理解的。 在C++语言的情况下，它的大小大约是它的五倍。C++上下文无关语法程序员阅读它应该没有什么困难。我们的方法还有进一步的优势，规范是可执行的，可以在实际程序上进行测试经过仔细的检查和测试，该规范可以为开发和验证提取器提供一致和完整的标准，并为事实库的用户提供对提取事实的含义和形式的清晰理解。Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-952事实抽取事实提取器可以被认为是从源程序到事实库的映射或转换。因此，事实提取的具体化可以分为三个部分：1) 域的指定（源语言的2) 范围的指定（事实库的语法），以及3) 从域到范围的映射。在我们的方法中，第一部分作为源程序的上下文无关语法给出。第二部分给出了事实库的形式或模式，也是作为一个上下文无关的语法。第三部分，映射，负责维护语义（或语义的特定方面），以便在输入结果事实库的工具处理解析后的源程序的一种常见机制是在内部将它们表示为抽象树（AST），我们的方法将使用这种机制。通过添加各种语义信息，AST可以被修饰为抽象语义图（ASG），通常至少是将变量引用连接到相应声明的链接。在Datrix的情况下，事实库代表ASG的一个变体，因此这种方法特别方便。如前所述，事实提取的范围，即，事实库的形式也可以被指定为另一种上下文无关语言。事实库可以被认为是ASG（可能是ASG的简化版本），它可以很容易地以具有上下文无关语法的形式表示。为了说明这一点，考虑这个C++表达式：a+ 3;在我们的案例研究中，此表达式的ASG的文本形式表示为：cOperator（op = bplus）{a：nameref（referes id=100） 3：literal}第一行表示这是一个加法表达式，括号表示变量a，常数3包含在表达式中或表达式的一部分中，其中a表示在其他地方定义的变量，并给出一个标识符100. ASG的这个片段给出了我们的方法如何将源程序转换为AST，然后转换为ASG，并最终转换为事实库的说明。从源程序到ASG的转换规范是96Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-是我们正式化的基础。 设计者的工作是为了使规范有效，转换的每一步都必须保证1）生成的ASG是格式良好的，即遵循ASG的语法，以及2）变换前的结构为了使具体化完整，它必须处理源语言的所有语法变化，即，与源上下文无关语法的所有部分我们相信，只有通过广泛的测试才能实现有效性，而我们方法的成功取决于可以自动测试我们规格的工具。幸运的是，这个工具已经存在。TXL是一种基于规则的语言，它对上下文无关语言执行转换。它可以输入我们的规范，并在源代码上执行我们规范中的转换。总之，我们在上下文无关文法中指定了源程序和ASG的语法，并且我们可以将从源程序到ASG的转换指定为上下文因为像TXL这样的工具支持我们的规范，所以我们可以使用测试来验证规范的一致性和完整性。3事实抽取形式化的好处我们对事实提取的形式化和基于上下文无关语法的转换的使用可以使模式设计者、事实提取器开发人员和事实提取器的用户受益。以下是我们将事实提取形式化的方法的四个主要好处：1) 语法与图式2) 明确各种模式3) 提取事实4) 核查事实提取者的依据。我们现在将详细描述这些3.1语法与图式的密切关系本文主要研究基于上下文无关文法解析源程序的事实抽取器。在这样的提取器中，可以预期事实库与源程序密切相关。我们指定事实提取的方法利用了这种接近性，从而最大限度地减少了事实提取规范的复杂性。这种方法要求设计者 以获得对源程序语法的透彻理解，Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-97事实库的形式。基于这种理解，设计者创建了一系列转换步骤，将源程序映射到其作为提取事实的表示，并仔细查看输入语法的所有部分都处理好了 我们的经验表明，创建这些转换是耗时的，并且需要检查和广泛的测试来确保规范的一致性和完整性。这个过程的一个副产品是，这些转换的复杂性是编写基于模式的事实提取器所需工作量的粗略指标。3.2明确各种模式在我们对Datrix [2]模式的提取版本进行形式化的经验中，我们发现从一组映射步骤开始将源代码转换为标准的中间表示是很方便的。这些步骤执行各种常见的内务处理功能，例如生成表示表达式和语句的正则化方式。这个标准的中间表示解决了可能存在的任何歧义在源程序中。然后，我们定义了进一步的转换，以将事实映射到Datrix模式定义的格式。我们希望创建从这个中间表示到其他模式（如Columbus模式）格式的转换集并不困难。[9]这种标准的中间模式可以节省模式设计者在特定语言（如C++）的细节我们的方法将转换分为一系列步骤。最初的步骤在很大程度上与最终提取事实的形式细节无关。最后的步骤对于不同的目标模式（如Datrix和Columbus）是特定的，可以进行比较以了解这些模式之间的关系。3.3提取事实我们的方法迫使模式的设计者仔细考虑源语言的具体语法。因此，规范更有可能是完整和一致的。因为一个可靠的模式对于信息交换是至关重要的，所以这项工作是值得的。使用不太严格的方法，存在事实提取器之间缺乏一致性的危险，因为模式的规范是模糊的，并且倾向于忽略低级但重要的细节。98Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-3.4事实提取者TXL [3][6]和类似的工具输入转换的规范，与相应的上下文无关语法集成，并对源代码执行转换。这意味着TXL可以被认为是我们的事实提取规范的机械解释器，因为我们的规范是基于一系列这样的转换。我们已经发现，我们在定义模式时使用的许多转换在这种情况下，我们可以编写反向转换。当目标模式是源完整的（包含足够的信息来重建源程序），或者接近于这样，我们可以使用这些反向转换来从事实库中恢复源代码。使用反向转换，我们验证了CPPX，这是由滑铁卢大学SWAG团队开发的事实提取器。在相关的工作中，Andrew Malton等人[5]提出了将事实提取视为图变换序列的想法。他们在2001年开发CPPX（C Plus Plus eXtractor）时使用了这种方法。相比之下，我们的方法使用基于上下文无关语法而不是图形的变换。我们的方法的优点是，它直接使用现有的基于语法的工具，如TXL。4案例研究：形式化Datrix模式这里描述的研究是SWAG团队的工作的一部分，以使事实提取更加准确和可靠。2000年，加拿大贝尔公司为C/C++程序的抽象语义图（ASG）创建了Datrix schema [2]。2001年，SWAG团队开发了CPPX（C++ FactExtractor）。这个事实提取器对GCC前端的输出执行一系列图形转换，直到它获得符合Datrix模式的事实库[5]。此外，SWAG团队还开发了RCPPX（反向CPPX），这是一种测试和验证CPPX生成的事实库的工具[11]。Bell Canada对Datrix架构的规范是非正式的。它通过给出C/C++的示例片段和ASG的相应示例片段来定义Datrix模式; ASG是嵌入了语义信息的AST。在Datrix模式中，AST由表示类型、声明、表达式和语句的节点树组成。语义信息作为属性（public、private、static或volatile等）添加到AST中。和语义边（从名称到名称的声明）。相比之下，我们的Datrix规范版本是一系列基于C++语法的转换，以满足Datrix模式。 因为ASG中的语义信息可以从AST中导出，我们将其划分为Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-99具体分为两部分：1）从C++到AST; 2）从AST到ASG。我们进一步将从C++到AST的转换分为四个步骤：1) 消除类型和变量中的歧义，2) 压扁，3) Post fixify，以及4) 生成Datrix AST。现在，我们将解释这四个步骤。4.1消除类型和变量的歧义C++语法[13]在类型和变量方面是不明确的。考虑这个程序片段：TypeOrVar * p;这个例子可以是两个变量TypeOrVar和p的乘法表达式，也可以是指向类型TypeOrVar的指针p的声明，如果TypeOrVar被定义为类型。这些歧义无法在上下文无关语法[1]的级别上解决，这意味着像TXL这样的工具无法在特定情况下直接我们的解决方案是引入一个oracle，这是一个区分名称和类型的程序。我们使用JLEX来生成这个程序。对于上面的例子，Oracle当它确定TypeOrVar是一种类型时，插入标记type>作为作为该步骤的结果，通过将程序片段变换为：TypeOrVar type> *p;消除歧义不是事实提取的内在要求，但这是非常可取的，否则提取的事实库会保留歧义，这可能导致后续工具的错误解释。因此，我们的方法消除了歧义。4.2变平我们将通过一个例子来解释这个过程。以下声明int x，y;（1）含义相同整数x;int n;（2）声明（1）更短，更方便程序员。然而，Datrix不允许这种较短的符号。在ASG中，每次变量引用x或y时，都会从该变量绘制一条指向x或y的引用边。因此，x和y必须是ASG中的单独节点。100Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-我们称声明（2）为声明（1）的扁平形式。简化形式通过减少表示等效源代码片段的方式来简化中间表示。该格式更接近目标ASG指定的Datrix模式。在声明的自动化过程中，我们使用上下文无关语言的转换，这可以通过TXL来实现，将声明转换为自动化的声明。 这个步骤的结果是每个声明只包含一个变量，并且变量的所有属性都是这个声明的一部分。4.3固定后最初的步骤标记任何模糊的变量或类型[4][7]，并标记所有声明。就AST而言，每个声明对应于一个特定的节点，每个语句或表达式对应于一个特定的子树。我们现在可以把程序看作是一系列独立的声明、表达式和语句。这些初始步骤对于创建Datrix以外的事实库（例如Columbia事实库）可能很有用。我们选择了表达式、语句和声明的post fix形式作为标准的中间表示。创建这种格式的子转换称为postfixify。post fix形式的表达式是众所周知的，但post fix形式的声明和语句并不经常使用，尽管它并不困难。在这一步完成之后，源程序变成了一系列post fix形式的语句、表达式和声明4.4生成Datrix AST第四步是生成Datrix AST。Datrix AST可以表示为括号表示的语言，其中子节点包含在括号内。从post fix表示到Datrix AST的转换在大多数情况下是直接的，因为Datrix AST的语法很简单。例如，在Datrix中，声明，C++语言中最复杂的部分，无论是内置类型，指针还是类，都是以下形式p：cObject{cPointerType{int：int}}这个例子将p声明为一个指向整数的指针。Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-1014.5从AST到ASG到目前为止，我们只处理了从源代码到AST的转换。要从AST创建ASG，我们仍然需要从名称引用到声明添加引用边由于不同作用域中的变量可以具有相同的名称，因此我们为ASG中的每个变量生成一个唯一的键（数字）。这种机制类似于符号表，只是更容易，因为AST的语法很简单。4.6我们方法一个正式的规范可能太长太复杂，以至于它的用处有限，这是一种危险。然而，通过我们的方法，事实提取的具体化并不特别长或复杂。大约是五倍只要是C++的上下文无关语法，程序员阅读它应该没有太大的困难。我们的方法还有一个更大的优点，即规范是可执行的，可以通过在实际程序上测试来验证。5结论我们的经验表明，形式化的事实提取可以提供一个有用的模式规范和不同模式之间的关系的清晰的理解因为这些规范中的大多数转换都可以通过程序操作工具（如TXL）实现，所以我们的规范也是一个强大的工具，可以验证规范和实际的事实提取器。当效率不是主要目标时，规范和TXL也可以作为事实提取器原型。我们的结论是，形式化的事实提取有可能有利于逆向工程，通过澄清语法和模式之间的关系，通过澄清各种模式之间的关系，通过提供一个清晰和明确的标准提取的事实，并作为基础，验证事实提取器。确认作者感谢审稿人为改进论文提出的宝贵意见。102Y. Lin，R.C. Holt / Electronic Notes in Theoretical Computer Science 94（2004）93-引用[1] M.N. Armstrong等人，评估建筑提取器，第五次逆向工程工作会议（WCRE 1998）9（1998），30[2] 加拿大贝尔公司，“DATRIX（tm）抽象语义图：参考手册”1.4版，加拿大贝尔公司，蒙特利尔，2000年。[3] J.R. Cordy等人，使用TXL转换系统进行软件工程中的源代码转换，源代码分析和操作特刊，信息和软件技术杂志44，139（2002年10月），827[4] A. Cox等人，IEEE软件维护国际会议（ICSM 2001）9（Nov.2001），12[5] T. R. Dean等人，UnionSchemas as a BasisforaC++ Extractor，Proceedings of WCRE2001：Working Conference on Reverse Engineering，Stuttgart，Germany 2001年10月9日[6] T. R. Dean等人，TXL中的语法编程，第二届IEEE源代码分析和操作国际研讨会论文集蒙特尔9（2002年10月）。[7] M. Favre，CPP指称语义，SCAM 2003，与ICSM 2003[8] R.放大图片作者：Richard C.霍尔特，莱纳·科施克，蒂博尔·吉莫西，《走向》aC/C++标准模式，WCRE 2001：逆向工程工作会议，德国斯图加特。9（2001年10月）。[9] 费 伦 茨 河 例 如 ， Columbus-Reverse EngineeringTooland Schema forC++ ，Proceedings of the International Conference on Software Maintenance（ICSM 2002），IEEEComputer Society9（2002）。[10] John C. Martin，“Introduction to Languages and the Theory of Computation”，第3版，McGraw-Hill，2003年。[11] 作者：Richard C.何德铭，一个事实抽取器的完整性，逆向工程工作会议，维多利亚BC加拿大。9（2003年11月）。[12] G. C. Murphy等人，静态调用图提取器的实证研究，ACM软件工程与方法学报，7（2）9（1998年4月），158[13] Bjarne Stroustrup，