如题所述
历史表明，重要数学概念对数学发展的作用是不可估量的，函数概念对数学发展的影响，可以说是贯穿古今、旷日持久、作用非凡，回顾函数概念的历史发展，看一看函数概念不断被精炼、深化、丰富的历史过程，是一件十分有益的事情，它不仅有助于我们提高对函数概念来龙去脉认识的清晰度，而且更能帮助我们领悟数学概念对数学发展，数学学习的巨大作用．
（一）
��马克思曾经认为，函数概念来源于代数学中不定方程的研究．由于罗马时代的丢番图对不定方程已有相当研究，所以函数概念至少在那时已经萌芽．
��自哥白尼的天文学革命以后，运动就成了文艺复兴时期科学家共同感兴趣的问题，人们在思索：既然地球不是宇宙中心，它本身又有自转和公转，那么下降的物体为什么不发生偏斜而还要垂直下落到地球上?行星运行的轨道是椭圆，原理是什么?还有，研究在地球表面上抛射物体的路线、射程和所能达到的高度，以及炮弹速度对于高度和射程的影响等问题，既是科学家的力图解决的问题，也是军事家要求解决的问题，函数概念就是从运动的研究中引申出的一个数学概念，这是函数概念的力学来源．
（二）
��早在函数概念尚未明确提出以前，数学家已经接触并研究了不少具体的函数，比如对数函数、三角函数、双曲函数等等．1673年前后笛卡儿在他的解析几何中，已经注意到了一个变量对于另一个变量的依赖关系，但由于当时尚未意识到需要提炼一般的函数概念，因此直到17世纪后期牛顿、莱布尼兹建立微积分的时候，数学家还没有明确函数的一般意义．
��1673年，莱布尼兹首次使用函数一词表示“幂”，后来他用该词表示曲线上点的横坐标、纵坐标、切线长等曲线上点的有关几何量．由此可以看出，函数一词最初的数学含义是相当广泛而较为模糊的，几乎与此同时，牛顿在微积分的讨论中，使用另一名词“流量”来表示变量间的关系，直到1689年，瑞士数学家约翰·贝努里才在莱布尼兹函数概念的基础上，对函数概念进行了明确定义，贝努里把变量x和常量按任何方式构成的量叫“x的函数”，表示为yx.
��当时，由于连接变数与常数的运算主要是算术运算、三角运算、指数运算和对数运算，所以后来欧拉就索性把用这些运算连接变数x和常数c而成的式子，取名为解析函数，还将它分成了“代数函数”与“超越函数”．
��18世纪中叶，由于研究弦振动问题，达朗贝尔与欧拉先后引出了“任意的函数”的说法．在解释“任意的函数”概念的时候，达朗贝尔说是指“任意的解析式”，而欧拉则认为是“任意画出的一条曲线”．现在看来这都是函数的表达方式，是函数概念的外延．
（三）
��函数概念缺乏科学的定义，引起了理论与实践的尖锐矛盾．例如，偏微分方程在工程技术中有广泛应用，但由于没有函数的科学定义，就极大地限制了偏微分方程理论的建立．1833年至1834年，高斯开始把注意力转向物理学．他在和W·威伯尔合作发明电报的过程中，做了许多关于磁的实验工作，提出了“力与距离的平方成反比例”这个重要的理论，使得函数作为数学的一个独立分支而出现了，实际的需要促使人们对函数的定义进一步研究．
��后来，人们又给出了这样的定义：如果一个量依赖着另一个量，当后一量变化时前一量也随着变化，那么第一个量称为第二个量的函数．“这个定义虽然还没有道出函数的本质，但却把变化、运动注入到函数定义中去，是可喜的进步．”
��在函数概念发展史上，法国数学家富里埃的工作影响最大，富里埃深刻地揭示了函数的本质，主张函数不必局限于解析表达式．1822年，他在名著《热的解析理论》中说，“通常，函数表示相接的一组值或纵坐标，它们中的每一个都是任意的……，我们不假定这些纵坐标服从一个共同的规律；他们以任何方式一个挨一个．”在该书中，他用一个三角级数和的形式表达了一个由不连续的“线”所给出的函数．更确切地说就是，任意一个以2π为周期函数，在〔－π，π〕区间内，可以由
�表示出，其中
��富里埃的研究，从根本上动摇了旧的关于函数概念的传统思想，在当时的数学界引起了很大的震动．原来，在解析式和曲线之间并不存在不可逾越的鸿沟，级数把解析式和曲线沟通了，那种视函数为解析式的观点终于成为揭示函数关系的巨大障碍．
��通过一场争论，产生了罗巴切夫斯基和狄里克莱的函数定义．
��1834年，俄国数学家罗巴切夫斯基提出函数的定义：“x的函数是这样的一个数，它对于每个x都有确定的值，并且随着x一起变化．函数值可以由解析式给出，也可以由一个条件给出，这个条件提供了一种寻求全部对应值的方法．函数的这种依赖关系可以存在，但仍然是未知的．”这个定义建立了变量与函数之间的对应关系，是对函数概念的一个重大发展，因为“对应”是函数概念的一种本质属性与核心部分．
��1837年，德国数学家狄里克莱（Dirichlet）认为怎样去建立x与y之间的关系无关紧要，所以他的定义是：“如果对于x的每一值，y总有完全确定的值与之对应，则y是x的函数．”
��根据这个定义，即使像如下表述的，它仍然被说成是函数（狄里克莱函数）：
f（x）= 1���（x为有理数），
0���（x为无理数）．
��在这个函数中，如果x由0逐渐增大地取值，则f（x）忽0忽1．在无论怎样小的区间里，f（x）无限止地忽0忽1．因此，它难用一个或几个式子来加以表示，甚至究竟能否找出表达式也是一个问题．但是不管其能否用表达式表示，在狄里克莱的定义下，这个f（x）仍是一个函数．
��狄里克莱的函数定义，出色地避免了以往函数定义中所有的关于依赖关系的描述，以完全清晰的方式为所有数学家无条件地接受．至此，我们已可以说，函数概念、函数的本质定义已经形成，这就是人们常说的经典函数定义．
（四）
��生产实践和科学实验的进一步发展，又引起函数概念新的尖锐矛盾，本世纪20年代，人类开始研究微观物理现象．1930年量子力学问世了，在量子力学中需要用到一种新的函数——δ-函数，
即�ρ（x）＝ 0，x≠0，
∞,x=0．
且
��δ-函数的出现，引起了人们的激烈争论．按照函数原来的定义，只允许数与数之间建立对应关系，而没有把“∞”作为数．另外，对于自变量只有一个点不为零的函数，其积分值却不等于零，这也是不可想象的．然而，δ-函数确实是实际模型的抽象．例如，当汽车、火车通过桥梁时，自然对桥梁产生压力．从理论上讲，车辆的轮子和桥面的接触点只有一个，设车辆对轨道、桥面的压力为一单位，这时在接触点x=0处的压强是
��P（0）=压力／接触面=1／0=∞．
��其余点x≠0处，因无压力，故无压强，即�P（x）=0.另外，我们知道压强函数的积分等于压力，即
�函数概念就在这样的历史条件下能动地向前发展，产生了新的现代函数定义：若对集合M的任意元素x,总有集合N确定的元素y与之对应，则称在集合M上定义一个函数，记为y=f（x）.元素x称为自变元，元素y称为因变元．
��函数的现代定义与经典定义从形式上看虽然只相差几个字，但却是概念上的重大发展，是数学发展道路上的重大转折，近代的泛函分析可以作为这种转折的标志，它研究的是一般集合上的函数关系．
��函数概念的定义经过二百多年来的锤炼、变革，形成了函数的现代定义，应该说已经相当完善了．不过数学的发展是无止境的，函数现代定义的形式并不意味着函数概念发展的历史终结，近二十年来，数学家们又把函数归结为一种更广泛的概念—“关系”．
��设集合X、Y，我们定义X与Y的积集X×Y为
��X×Y=｛（x,y）｜x∈X,y∈Y｝．
��积集X×Y中的一子集R称为X与Y的一个关系，若（x,y）∈R，则称x与y有关系R，记为xRy.若（x,y）R，则称x与y无关系．
��现设f是X与Y的关系，即fX×Y，如果（x,y），（x,z）∈f,必有y=z，那么称f为X到Y的函数．在此定义中，已在形式上回避了“对应”的术语，全部使用集合论的语言了．
��从以上函数概念发展的全过程中，我们体会到，联系实际、联系大量数学素材，研究、发掘、拓广数学概念的内涵是何等重要．
（一）
��马克思曾经认为，函数概念来源于代数学中不定方程的研究．由于罗马时代的丢番图对不定方程已有相当研究，所以函数概念至少在那时已经萌芽．
��自哥白尼的天文学革命以后，运动就成了文艺复兴时期科学家共同感兴趣的问题，人们在思索：既然地球不是宇宙中心，它本身又有自转和公转，那么下降的物体为什么不发生偏斜而还要垂直下落到地球上?行星运行的轨道是椭圆，原理是什么?还有，研究在地球表面上抛射物体的路线、射程和所能达到的高度，以及炮弹速度对于高度和射程的影响等问题，既是科学家的力图解决的问题，也是军事家要求解决的问题，函数概念就是从运动的研究中引申出的一个数学概念，这是函数概念的力学来源．
（二）
��早在函数概念尚未明确提出以前，数学家已经接触并研究了不少具体的函数，比如对数函数、三角函数、双曲函数等等．1673年前后笛卡儿在他的解析几何中，已经注意到了一个变量对于另一个变量的依赖关系，但由于当时尚未意识到需要提炼一般的函数概念，因此直到17世纪后期牛顿、莱布尼兹建立微积分的时候，数学家还没有明确函数的一般意义．
��1673年，莱布尼兹首次使用函数一词表示“幂”，后来他用该词表示曲线上点的横坐标、纵坐标、切线长等曲线上点的有关几何量．由此可以看出，函数一词最初的数学含义是相当广泛而较为模糊的，几乎与此同时，牛顿在微积分的讨论中，使用另一名词“流量”来表示变量间的关系，直到1689年，瑞士数学家约翰·贝努里才在莱布尼兹函数概念的基础上，对函数概念进行了明确定义，贝努里把变量x和常量按任何方式构成的量叫“x的函数”，表示为yx.
��当时，由于连接变数与常数的运算主要是算术运算、三角运算、指数运算和对数运算，所以后来欧拉就索性把用这些运算连接变数x和常数c而成的式子，取名为解析函数，还将它分成了“代数函数”与“超越函数”．
��18世纪中叶，由于研究弦振动问题，达朗贝尔与欧拉先后引出了“任意的函数”的说法．在解释“任意的函数”概念的时候，达朗贝尔说是指“任意的解析式”，而欧拉则认为是“任意画出的一条曲线”．现在看来这都是函数的表达方式，是函数概念的外延．
（三）
��函数概念缺乏科学的定义，引起了理论与实践的尖锐矛盾．例如，偏微分方程在工程技术中有广泛应用，但由于没有函数的科学定义，就极大地限制了偏微分方程理论的建立．1833年至1834年，高斯开始把注意力转向物理学．他在和W·威伯尔合作发明电报的过程中，做了许多关于磁的实验工作，提出了“力与距离的平方成反比例”这个重要的理论，使得函数作为数学的一个独立分支而出现了，实际的需要促使人们对函数的定义进一步研究．
��后来，人们又给出了这样的定义：如果一个量依赖着另一个量，当后一量变化时前一量也随着变化，那么第一个量称为第二个量的函数．“这个定义虽然还没有道出函数的本质，但却把变化、运动注入到函数定义中去，是可喜的进步．”
��在函数概念发展史上，法国数学家富里埃的工作影响最大，富里埃深刻地揭示了函数的本质，主张函数不必局限于解析表达式．1822年，他在名著《热的解析理论》中说，“通常，函数表示相接的一组值或纵坐标，它们中的每一个都是任意的……，我们不假定这些纵坐标服从一个共同的规律；他们以任何方式一个挨一个．”在该书中，他用一个三角级数和的形式表达了一个由不连续的“线”所给出的函数．更确切地说就是，任意一个以2π为周期函数，在〔－π，π〕区间内，可以由
�表示出，其中
��富里埃的研究，从根本上动摇了旧的关于函数概念的传统思想，在当时的数学界引起了很大的震动．原来，在解析式和曲线之间并不存在不可逾越的鸿沟，级数把解析式和曲线沟通了，那种视函数为解析式的观点终于成为揭示函数关系的巨大障碍．
��通过一场争论，产生了罗巴切夫斯基和狄里克莱的函数定义．
��1834年，俄国数学家罗巴切夫斯基提出函数的定义：“x的函数是这样的一个数，它对于每个x都有确定的值，并且随着x一起变化．函数值可以由解析式给出，也可以由一个条件给出，这个条件提供了一种寻求全部对应值的方法．函数的这种依赖关系可以存在，但仍然是未知的．”这个定义建立了变量与函数之间的对应关系，是对函数概念的一个重大发展，因为“对应”是函数概念的一种本质属性与核心部分．
��1837年，德国数学家狄里克莱（Dirichlet）认为怎样去建立x与y之间的关系无关紧要，所以他的定义是：“如果对于x的每一值，y总有完全确定的值与之对应，则y是x的函数．”
��根据这个定义，即使像如下表述的，它仍然被说成是函数（狄里克莱函数）：
f（x）= 1���（x为有理数），
0���（x为无理数）．
��在这个函数中，如果x由0逐渐增大地取值，则f（x）忽0忽1．在无论怎样小的区间里，f（x）无限止地忽0忽1．因此，它难用一个或几个式子来加以表示，甚至究竟能否找出表达式也是一个问题．但是不管其能否用表达式表示，在狄里克莱的定义下，这个f（x）仍是一个函数．
��狄里克莱的函数定义，出色地避免了以往函数定义中所有的关于依赖关系的描述，以完全清晰的方式为所有数学家无条件地接受．至此，我们已可以说，函数概念、函数的本质定义已经形成，这就是人们常说的经典函数定义．
（四）
��生产实践和科学实验的进一步发展，又引起函数概念新的尖锐矛盾，本世纪20年代，人类开始研究微观物理现象．1930年量子力学问世了，在量子力学中需要用到一种新的函数——δ-函数，
即�ρ（x）＝ 0，x≠0，
∞,x=0．
且
��δ-函数的出现，引起了人们的激烈争论．按照函数原来的定义，只允许数与数之间建立对应关系，而没有把“∞”作为数．另外，对于自变量只有一个点不为零的函数，其积分值却不等于零，这也是不可想象的．然而，δ-函数确实是实际模型的抽象．例如，当汽车、火车通过桥梁时，自然对桥梁产生压力．从理论上讲，车辆的轮子和桥面的接触点只有一个，设车辆对轨道、桥面的压力为一单位，这时在接触点x=0处的压强是
��P（0）=压力／接触面=1／0=∞．
��其余点x≠0处，因无压力，故无压强，即�P（x）=0.另外，我们知道压强函数的积分等于压力，即
�函数概念就在这样的历史条件下能动地向前发展，产生了新的现代函数定义：若对集合M的任意元素x,总有集合N确定的元素y与之对应，则称在集合M上定义一个函数，记为y=f（x）.元素x称为自变元，元素y称为因变元．
��函数的现代定义与经典定义从形式上看虽然只相差几个字，但却是概念上的重大发展，是数学发展道路上的重大转折，近代的泛函分析可以作为这种转折的标志，它研究的是一般集合上的函数关系．
��函数概念的定义经过二百多年来的锤炼、变革，形成了函数的现代定义，应该说已经相当完善了．不过数学的发展是无止境的，函数现代定义的形式并不意味着函数概念发展的历史终结，近二十年来，数学家们又把函数归结为一种更广泛的概念—“关系”．
��设集合X、Y，我们定义X与Y的积集X×Y为
��X×Y=｛（x,y）｜x∈X,y∈Y｝．
��积集X×Y中的一子集R称为X与Y的一个关系，若（x,y）∈R，则称x与y有关系R，记为xRy.若（x,y）R，则称x与y无关系．
��现设f是X与Y的关系，即fX×Y，如果（x,y），（x,z）∈f,必有y=z，那么称f为X到Y的函数．在此定义中，已在形式上回避了“对应”的术语，全部使用集合论的语言了．
��从以上函数概念发展的全过程中，我们体会到，联系实际、联系大量数学素材，研究、发掘、拓广数学概念的内涵是何等重要．
温馨提示：答案为网友推荐，仅供参考
第1个回答 2006-10-04
反编译在航天工业中的应用*
赵 蕾 吴 岩 王开铸
(哈尔滨工业大学计算机系319信箱*哈尔滨*150001)
摘 要 本文论述了反编译作为一种程序验证的工具在航天工业中的重要地位和应用;介绍了反编译的背景知识;给出一个实用的反编译系统DCPL的设计模型和关键技术及其一个运行结果示例以说明反编译器的功能。
主题词 反编译 软件工具 程序验证 程序可靠性
APPLICATION OF DECOMPILATION
TO AEROSPACE INDUSTRY
Zhao Lei Wu Yan Wang Kaizhu
(Department of Computer Science and Engineering
BOX 319,Harbin Institute of Technology*Harbin*150001)
Abstract In this paper,the significance and application of decompilation as a program verifying tool in Aerospace Industry is discussed;the background knowledge of decompilation is introduced;a model of a practical decompiler DCPL is presented as well its result to show its function.
Key words Decompilation Software tool Program verification Program reliability
1 引 言
航天工业是各国竞相发展的一项事业。航天器的各部分都离不开计算机的控制,各种控制软件、计算软件、分析软件等等在航天器的设计与应用中起着重要地位。
1996年6月4日阿里亚娜-5型火箭发射失事,使欧共体蒙受25亿美元以上的损失。经过专家调查,此次失事的主要原因是:箭载计算机系统使用的软件出了问题。此软件是从阿里亚娜-4型火箭的软件系统中移植过来的,由于5型火箭上增加了新机构,而4型火箭的软件不能对这些新机构发出的信号进行分析和处理,从而导致火箭控制失灵。由于阿里亚娜-5型火箭发射的失事,使软件可靠性和正确性问题再度摆到软件开发者面前〔1〕。反编译器作为一种有效的程序验证的工具使人们再度意识到它在航天工业中的重要性及实用性。本文介绍了反编译器的功能、产生背景和它在航天工业中的应用,并给出了我们正在研制的一个实用反编译系统DCPL的体系结构及关键技术,最后给出其一个简单的运行示例。
2 反编译的背景知识介绍
2.1 反编译的定义
反编译可以看成是编译的逆过程,即将以机器语言形式存在的目标代码翻译成与其功能等价的高级语言形式的代码的过程〔2〕。
确定型反编译的模型为一个映射,decompile:S—＞T,其中S是源代码集(source),是机器指令集;T是目标代码集(target),是高级语句集。
2.2 反编译的产生背景
反编译(Decompilation)一词第一次出现于1960年。六十年代,随着第三代计算机的产生,为了挽救大量的运行在即将报废的第二代计算机上的软年,同时也为加速开发第三代机器的软件,美国开始研制专门用途的反编译器作为软件移植的工具。
2.3 反编译在航天技术中的应用
反编译发展至今,其应用领域主要体现在软件维护和软件安全性〔2〕两方面。用于软件维护时,主要是恢复丢失的源代码、将软件移植到新的硬件平台、重新结构化旧有软件等等。用于软件安全性时,主要是针对安全性要求极高(safty-critical)的软件,发现其中是否有病毒,或是否有隐藏的窃密程序(Trojan)。
西方各国早已将反编译技术用于航天事业和尖端工业,如:IBM为NASA的航天飞机研制的反编译器〔3〕;澳大利亚电子研究实验室研制的针对类Pascal语言的反编译器〔4〕;欧共体ESPRIT计划中的反编译研究,如英国的核工业部使用反编译技术验证大量的safty-critical软件,以提高软件的正确性〔5〕;我国从80年代初开始反编译的研究并且已逐步形成自己的产品〔6〕,但尚未见将反编译技术应用于航天技术的报导。
用于航天的软件系统通常不经过编译优化以避免不必要的软件错误,反编译此类软件的难度相对减小。可以通过将内存映象的反编译结果与原始输入(源程序)相比较来验证软件的正确性,如果二程序完全等价,则编译结果可靠(反编译可靠的前提下)。如下图示:
图1 反编译验证程序正确性
如果对于每一种输入,都有输出1=输出2=预测结果,则可说明编译是可靠的。同样也可通过比较原始程序和反编译结果在程序功能空间中的拓朴结构是否完全一样,来判定反编译是否做到了输出结果与原始程序功能等价,这通常要经过大量的测试。
3 一个实用反编译系统DCPL的体系结构
DCPL是我们研制的一个反编译系统,其设计吸收了编译技术中的成熟理论。
3.1 DCPL体系结构
下图给出了DCPL的模型。它以可执行文件作为输入,输出与其对应的C语言程序。
图2 DCPL体系结构
3.2 DCPL各模块的功能
(1)预处理器:是DCPL的基础,以可执行文件作为输入,将其部分反汇编,根据程序的启动代码,提取出相应的数据段和代码段,存储在中间文件中。
(2)库函数识别器:是对中间文件的一遍扫描。根据库函数特征表识别出文件中所有库函数和用户自定义函数的入口。采用顺序-索引-连接技术构造特征表。索引函数的形式为:index(len,n)=w1*len+w2*n;其中len和n分别为函数主体的长度和它所调用辅函数的次数。用一指针数组指向各个特征链的头结点,数组的下标值是索引函数作用于各个特征结点上的结果;同一个链上的各个结点的特征值经索引函数作用后其值相同;链表内部,各结点依照使用频率顺序存放。
(3)控制流分析器:根据反编译控制流文法,以语法制导的方法进行控制流的分析和归约,生成控制流模块的机内表示形式及其结构文件。采用约束属性文法描述控制流,如<for>∷=jmp{statement}m0{cmp}<jop>
｜jmp.destination=cmp.offset&&jop.destination=statement.offset｜之后的是该规则的约束。用移进-归约策略和模式匹配方法相结合进行分析和归约。
(4)数据流分析器:根据库函数识别器提供的库函数参数信息和函数返回值信息、控制流分析器得到的基本块划分信息进行变量恢复。具体实现时分两步走:<1>变量定值-应用信息的收集和综合
为每个变量构造定值-应用链。其模型是双向链表,如下图所示:
图3 定值-应用链的一个结点模型
定值-应用链是记录变量定义和使用信息的数据结构,其define指针指向定义它的语句,use指针指向在它被重定义之前所有使用它的语句(即该变量出现在赋值语句右边的情况)。定值-应用链可以推理相关联的简单类型变量的类型(字符型、整型等)。
<2>变量类型的推理分析
把变量放在上下文中,利用推理规则进行再求精。求精过程利用了汉语处理中的分词思想。将同时出现次数超过阈值的一组内存单元和寄存器绑在一起,形成一个token(一个复杂的数据类型),阈值可根据结果进行调整。这是一个反馈过程,用于恢复复合数据类型(数组、结构等),规则型如:call a〔〕-＞initiate array;exist(loop,index si,base bx)-＞assign array;(add ax,adc dx)-＞addition long等等。推理分析结果的正确性依赖于复合数据是否是同时引用和规则的完备性,是个不确定性算法。
(5)优化器:将前几个模块生成的结果进行综合分析,去除冗余变量和中间语句,如中间变量和指令,进行语句的合并和流程的结构化。
(6)翻译器:将前述模块生成的机内表示形式翻译成C语言程序形式,输出给用户,完成反编译的任务。
3.3 系统的一个运行结果举例
下面是一个简单的C语言程序以及其目标代码的反汇编形式和应用于DCPL的输出结果。
测试用C语言程序:
main()
{ int a,b,c;
scanf(〃%d〃,&a);
if(a＞=0)
{ if(a＞20)
{b=a;
c=b+2;}
else
c=a; }
else
{ c=a;
b=c*a;}
printf(〃%d〃,c); }
DCPL的输出结果:
main()
{ int var1;
register int var2;
register int var3;
scanf(〃%d〃,&var1);
if(var1＞=0)
{ if(var1＞20)
{ var2=var1;
var3=var2+2;}
else
{ var3=var1;}}
else
{ var3=var1;
var2=var3*var1;}
printf(〃%d〃,var3); }
测试用C语言程序所对应的目标代码:
2386:01FA 55 PUSH BP
2386:01FD 8BECMOVBP,SP
2386:01FD 83EC02SUBSPM+02
2386:0200 56PUSHSI
2386:0201 57PUSHDI
2386:0202 8D46FELEAAX,〔BP-02〕
2386:0205 50PUSHAX
2386:0206 B89401MOVAX,0194
2386:0209 50PUSHAX
2386:020A E86714CALL1674
2386:020D 59POPCX
2386:020E 59POPCX
2386:020F 837EFE00CMPWORD PTR〔BP-02〕,+00
2386:0213 7C14JL0229
2386:0215 837EFE14CMPWORD PTR〔BP-02〕,+14
2386:0219 7E09JLE0224
2386:021B 8B7EFEMOVDI,〔BP-02〕
2386:021E 8BF7MOVSI,DI
2386:0220 46INCSI
2386:0221 46INCSI
2386:0222 EB03JMP0227
2386:0224 8B76FEMOVSI,〔BP-02〕
2386:0227 EB0AJMP0233
2386:0229 8B76FEMOVSI,〔BP-02〕
2386:022C 8BC6MOVAX,SI
2386:022E F766FEMULWORD PTR〔BP-02〕
2386:0231 8BF8MOVDI,AX
2386:0233 56PUSHSI
2386:0234 B89701MOVAX,0197
2386:0237 50PUSHAX
2386:0238 E8990BCALL0DD4
2386:023B 59POPCX
2386:023C 59POPCX
2386:020D 5FPOPDI
2386:020E 5EPOPSI
2386:023F 8BE5MOVSP,BP
2386:0241 5DPOPBP
2386:0242 C3RET
4 结束语
发展航天事业是我国的一项国策,航天计划的成功完成是众望所向。近几年各国因航天器的软件可靠性较差导致的种种航天发射失败所造成的不必要的人员伤亡和财政浪费,使得软件正确性验证日益显现出重要性。反编译正是解决这一课题的极佳工具。我国在该课题上的研究尽管起步较国外晚,但现已取得了长足的进展。经济国内反编译同行的研究和实践,现有的反编译系统基本达到了验证简单程序的要求,但要反编译大规模的软件,诸如用于航天计划中的软件,还需要深入的研究。将反编译技术应用于航天领域以提高航天器材的可靠性,航天发射的成功率,航天器运行的正确性,确实是一个很有前途的研究方向。
参考文献
1 李未.欧洲程序设计方法研究的三个动向.智能机研研究动态,Vol 9,1996
2 Cristina Cifuentes and John Gough K.Decompilation of binary programs.Software Practice and Experience,1995,25(7)
3 Spector A and Gifford D.Case study:the space shuttle primary computer system,Communications of the ACM,27,872-900
4 Hood S T.Decompiling with definite clause grammars.Research Report,ERL-0571-RR,1991
5 Pavey D J and Winsborrow L A.Demonstrating equivalence of source code and PROM contents.4th European Workshop on Dependable Commputing,8-10,1992
6 合肥工业大学微机所.DECLER用户使用手册.1995.3
赵 蕾 吴 岩 王开铸
(哈尔滨工业大学计算机系319信箱*哈尔滨*150001)
摘 要 本文论述了反编译作为一种程序验证的工具在航天工业中的重要地位和应用;介绍了反编译的背景知识;给出一个实用的反编译系统DCPL的设计模型和关键技术及其一个运行结果示例以说明反编译器的功能。
主题词 反编译 软件工具 程序验证 程序可靠性
APPLICATION OF DECOMPILATION
TO AEROSPACE INDUSTRY
Zhao Lei Wu Yan Wang Kaizhu
(Department of Computer Science and Engineering
BOX 319,Harbin Institute of Technology*Harbin*150001)
Abstract In this paper,the significance and application of decompilation as a program verifying tool in Aerospace Industry is discussed;the background knowledge of decompilation is introduced;a model of a practical decompiler DCPL is presented as well its result to show its function.
Key words Decompilation Software tool Program verification Program reliability
1 引 言
航天工业是各国竞相发展的一项事业。航天器的各部分都离不开计算机的控制,各种控制软件、计算软件、分析软件等等在航天器的设计与应用中起着重要地位。
1996年6月4日阿里亚娜-5型火箭发射失事,使欧共体蒙受25亿美元以上的损失。经过专家调查,此次失事的主要原因是:箭载计算机系统使用的软件出了问题。此软件是从阿里亚娜-4型火箭的软件系统中移植过来的,由于5型火箭上增加了新机构,而4型火箭的软件不能对这些新机构发出的信号进行分析和处理,从而导致火箭控制失灵。由于阿里亚娜-5型火箭发射的失事,使软件可靠性和正确性问题再度摆到软件开发者面前〔1〕。反编译器作为一种有效的程序验证的工具使人们再度意识到它在航天工业中的重要性及实用性。本文介绍了反编译器的功能、产生背景和它在航天工业中的应用,并给出了我们正在研制的一个实用反编译系统DCPL的体系结构及关键技术,最后给出其一个简单的运行示例。
2 反编译的背景知识介绍
2.1 反编译的定义
反编译可以看成是编译的逆过程,即将以机器语言形式存在的目标代码翻译成与其功能等价的高级语言形式的代码的过程〔2〕。
确定型反编译的模型为一个映射,decompile:S—＞T,其中S是源代码集(source),是机器指令集;T是目标代码集(target),是高级语句集。
2.2 反编译的产生背景
反编译(Decompilation)一词第一次出现于1960年。六十年代,随着第三代计算机的产生,为了挽救大量的运行在即将报废的第二代计算机上的软年,同时也为加速开发第三代机器的软件,美国开始研制专门用途的反编译器作为软件移植的工具。
2.3 反编译在航天技术中的应用
反编译发展至今,其应用领域主要体现在软件维护和软件安全性〔2〕两方面。用于软件维护时,主要是恢复丢失的源代码、将软件移植到新的硬件平台、重新结构化旧有软件等等。用于软件安全性时,主要是针对安全性要求极高(safty-critical)的软件,发现其中是否有病毒,或是否有隐藏的窃密程序(Trojan)。
西方各国早已将反编译技术用于航天事业和尖端工业,如:IBM为NASA的航天飞机研制的反编译器〔3〕;澳大利亚电子研究实验室研制的针对类Pascal语言的反编译器〔4〕;欧共体ESPRIT计划中的反编译研究,如英国的核工业部使用反编译技术验证大量的safty-critical软件,以提高软件的正确性〔5〕;我国从80年代初开始反编译的研究并且已逐步形成自己的产品〔6〕,但尚未见将反编译技术应用于航天技术的报导。
用于航天的软件系统通常不经过编译优化以避免不必要的软件错误,反编译此类软件的难度相对减小。可以通过将内存映象的反编译结果与原始输入(源程序)相比较来验证软件的正确性,如果二程序完全等价,则编译结果可靠(反编译可靠的前提下)。如下图示:
图1 反编译验证程序正确性
如果对于每一种输入,都有输出1=输出2=预测结果,则可说明编译是可靠的。同样也可通过比较原始程序和反编译结果在程序功能空间中的拓朴结构是否完全一样,来判定反编译是否做到了输出结果与原始程序功能等价,这通常要经过大量的测试。
3 一个实用反编译系统DCPL的体系结构
DCPL是我们研制的一个反编译系统,其设计吸收了编译技术中的成熟理论。
3.1 DCPL体系结构
下图给出了DCPL的模型。它以可执行文件作为输入,输出与其对应的C语言程序。
图2 DCPL体系结构
3.2 DCPL各模块的功能
(1)预处理器:是DCPL的基础,以可执行文件作为输入,将其部分反汇编,根据程序的启动代码,提取出相应的数据段和代码段,存储在中间文件中。
(2)库函数识别器:是对中间文件的一遍扫描。根据库函数特征表识别出文件中所有库函数和用户自定义函数的入口。采用顺序-索引-连接技术构造特征表。索引函数的形式为:index(len,n)=w1*len+w2*n;其中len和n分别为函数主体的长度和它所调用辅函数的次数。用一指针数组指向各个特征链的头结点,数组的下标值是索引函数作用于各个特征结点上的结果;同一个链上的各个结点的特征值经索引函数作用后其值相同;链表内部,各结点依照使用频率顺序存放。
(3)控制流分析器:根据反编译控制流文法,以语法制导的方法进行控制流的分析和归约,生成控制流模块的机内表示形式及其结构文件。采用约束属性文法描述控制流,如<for>∷=jmp{statement}m0{cmp}<jop>
｜jmp.destination=cmp.offset&&jop.destination=statement.offset｜之后的是该规则的约束。用移进-归约策略和模式匹配方法相结合进行分析和归约。
(4)数据流分析器:根据库函数识别器提供的库函数参数信息和函数返回值信息、控制流分析器得到的基本块划分信息进行变量恢复。具体实现时分两步走:<1>变量定值-应用信息的收集和综合
为每个变量构造定值-应用链。其模型是双向链表,如下图所示:
图3 定值-应用链的一个结点模型
定值-应用链是记录变量定义和使用信息的数据结构,其define指针指向定义它的语句,use指针指向在它被重定义之前所有使用它的语句(即该变量出现在赋值语句右边的情况)。定值-应用链可以推理相关联的简单类型变量的类型(字符型、整型等)。
<2>变量类型的推理分析
把变量放在上下文中,利用推理规则进行再求精。求精过程利用了汉语处理中的分词思想。将同时出现次数超过阈值的一组内存单元和寄存器绑在一起,形成一个token(一个复杂的数据类型),阈值可根据结果进行调整。这是一个反馈过程,用于恢复复合数据类型(数组、结构等),规则型如:call a〔〕-＞initiate array;exist(loop,index si,base bx)-＞assign array;(add ax,adc dx)-＞addition long等等。推理分析结果的正确性依赖于复合数据是否是同时引用和规则的完备性,是个不确定性算法。
(5)优化器:将前几个模块生成的结果进行综合分析,去除冗余变量和中间语句,如中间变量和指令,进行语句的合并和流程的结构化。
(6)翻译器:将前述模块生成的机内表示形式翻译成C语言程序形式,输出给用户,完成反编译的任务。
3.3 系统的一个运行结果举例
下面是一个简单的C语言程序以及其目标代码的反汇编形式和应用于DCPL的输出结果。
测试用C语言程序:
main()
{ int a,b,c;
scanf(〃%d〃,&a);
if(a＞=0)
{ if(a＞20)
{b=a;
c=b+2;}
else
c=a; }
else
{ c=a;
b=c*a;}
printf(〃%d〃,c); }
DCPL的输出结果:
main()
{ int var1;
register int var2;
register int var3;
scanf(〃%d〃,&var1);
if(var1＞=0)
{ if(var1＞20)
{ var2=var1;
var3=var2+2;}
else
{ var3=var1;}}
else
{ var3=var1;
var2=var3*var1;}
printf(〃%d〃,var3); }
测试用C语言程序所对应的目标代码:
2386:01FA 55 PUSH BP
2386:01FD 8BECMOVBP,SP
2386:01FD 83EC02SUBSPM+02
2386:0200 56PUSHSI
2386:0201 57PUSHDI
2386:0202 8D46FELEAAX,〔BP-02〕
2386:0205 50PUSHAX
2386:0206 B89401MOVAX,0194
2386:0209 50PUSHAX
2386:020A E86714CALL1674
2386:020D 59POPCX
2386:020E 59POPCX
2386:020F 837EFE00CMPWORD PTR〔BP-02〕,+00
2386:0213 7C14JL0229
2386:0215 837EFE14CMPWORD PTR〔BP-02〕,+14
2386:0219 7E09JLE0224
2386:021B 8B7EFEMOVDI,〔BP-02〕
2386:021E 8BF7MOVSI,DI
2386:0220 46INCSI
2386:0221 46INCSI
2386:0222 EB03JMP0227
2386:0224 8B76FEMOVSI,〔BP-02〕
2386:0227 EB0AJMP0233
2386:0229 8B76FEMOVSI,〔BP-02〕
2386:022C 8BC6MOVAX,SI
2386:022E F766FEMULWORD PTR〔BP-02〕
2386:0231 8BF8MOVDI,AX
2386:0233 56PUSHSI
2386:0234 B89701MOVAX,0197
2386:0237 50PUSHAX
2386:0238 E8990BCALL0DD4
2386:023B 59POPCX
2386:023C 59POPCX
2386:020D 5FPOPDI
2386:020E 5EPOPSI
2386:023F 8BE5MOVSP,BP
2386:0241 5DPOPBP
2386:0242 C3RET
4 结束语
发展航天事业是我国的一项国策,航天计划的成功完成是众望所向。近几年各国因航天器的软件可靠性较差导致的种种航天发射失败所造成的不必要的人员伤亡和财政浪费,使得软件正确性验证日益显现出重要性。反编译正是解决这一课题的极佳工具。我国在该课题上的研究尽管起步较国外晚,但现已取得了长足的进展。经济国内反编译同行的研究和实践,现有的反编译系统基本达到了验证简单程序的要求,但要反编译大规模的软件,诸如用于航天计划中的软件,还需要深入的研究。将反编译技术应用于航天领域以提高航天器材的可靠性,航天发射的成功率,航天器运行的正确性,确实是一个很有前途的研究方向。
参考文献
1 李未.欧洲程序设计方法研究的三个动向.智能机研研究动态,Vol 9,1996
2 Cristina Cifuentes and John Gough K.Decompilation of binary programs.Software Practice and Experience,1995,25(7)
3 Spector A and Gifford D.Case study:the space shuttle primary computer system,Communications of the ACM,27,872-900
4 Hood S T.Decompiling with definite clause grammars.Research Report,ERL-0571-RR,1991
5 Pavey D J and Winsborrow L A.Demonstrating equivalence of source code and PROM contents.4th European Workshop on Dependable Commputing,8-10,1992
6 合肥工业大学微机所.DECLER用户使用手册.1995.3
