函数的发展史论文参考文献

函数概念的发展历史1.早期函数概念——几何观念下的函数十七世纪伽俐略(G．Galileo，意，1564－1642)在《两门新科学》一书中，几乎全部包含函数或称为变量关系的这一概念，用文字和比例的语言表达函数的关系。1673年前后笛卡尔(Descartes，法，1596－1650)在他的解析几何中，已注意到一个变量对另一个变量的依赖关系，但因当时尚未意识到要提炼函数概念，因此直到17世纪后期牛顿、莱布尼兹建立微积分时还没有人明确函数的一般意义，大部分函数是被当作曲线来研究的。1673年，莱布尼兹首次使用“function” （函数）表示“幂”，后来他用该词表示曲线上点的横坐标、纵坐标、切线长等曲线上点的有关几何量。与此同时，牛顿在微积分的讨论中，使用 “流量”来表示变量间的关系。2.十八世纪函数概念──代数观念下的函数1718年约翰??贝努利(Bernoulli Johann，瑞，1667－1748)在莱布尼兹函数概念的基础上对函数概念进行了定义：“由任一变量和常数的任一形式所构成的量。”他的意思是凡变量x和常量构成的式子都叫做x的函数，并强调函数要用公式来表示。1755，欧拉(L．Euler，瑞士，1707－1783) 把函数定义为“如果某些变量，以某一种方式依赖于另一些变量，即当后面这些变量变化时，前面这些变量也随着变化，我们把前面的变量称为后面变量的函数。”18世纪中叶欧拉(L．Euler，瑞，1707－1783)给出了定义：“一个变量的函数是由这个变量和一些数即常数以任何方式组成的解析表达式。”他把约翰??贝努利给出的函数定义称为解析函数，并进一步把它区分为代数函数和超越函数，还考虑了“随意函数”。不难看出，欧拉给出的函数定义比约翰??贝努利的定义更普遍、更具有广泛意义。3.十九世纪函数概念──对应关系下的函数1821年，柯西(Cauchy，法，1789－1857) 从定义变量起给出了定义：“在某些变数间存在着一定的关系，当一经给定其中某一变数的值，其他变数的值可随着而确定时，则将最初的变数叫自变量，其他各变数叫做函数。”在柯西的定义中，首先出现了自变量一词，同时指出对函数来说不一定要有解析表达式。不过他仍然认为函数关系可以用多个解析式来表示，这是一个很大的局限。1822年傅里叶（Fourier，法国，1768——1830）发现某些函数也已用曲线表示，也可以用一个式子表示，或用多个式子表示，从而结束了函数概念是否以唯一一个式子表示的争论，把对函数的认识又推进了一个新层次。1837年狄利克雷(Dirichlet，德，1805－1859) 突破了这一局限，认为怎样去建立x与y之间的关系无关紧要，他拓广了函数概念，指出：“对于在某区间上的每一个确定的x值，y都有一个或多个确定的值，那么y叫做x的函数。”这个定义避免了函数定义中对依赖关系的描述，以清晰的方式被所有数学家接受。这就是人们常说的经典函数定义。等到康托(Cantor，德，1845－1918)创立的集合论在数学中占有重要地位之后，维布伦(Veblen，美，1880－1960)用“集合”和“对应”的概念给出了近代函数定义，通过集合概念把函数的对应关系、定义域及值域进一步具体化了，且打破了“变量是数”的极限，变量可以是数，也可以是其它对象。4.现代函数概念──集合论下的函数1914年豪斯道夫(F．Hausdorff)在《集合论纲要》中用不明确的概念“序偶”来定义函数，其避开了意义不明确的“变量”、“对应”概念。库拉托夫斯基(Kuratowski)于1921年用集合概念来定义“序偶”使豪斯道夫的定义很严谨了。1930 年新的现代函数定义为“若对集合M的任意元素x，总有集合N确定的元素y与之对应，则称在集合M上定义一个函数，记为y=f(x)。元素x称为自变元，元素y称为因变元。”术语函数，映射，对应，变换通常都有同一个意思。但函数只表示数与数之间的对应关系，映射还可表示点与点之间，图形之间等的对应关系。可以说函数包含于映射。当然，映射也只是一部分。 [编辑本段]幂函数幂函数的一般形式为y=x^a。如果a取非零的有理数是比较容易理解的，不过初学者对于a取无理数，则不太容易理解，在我们的课程里，不要求掌握如何理解指数为无理数的问题，因为这涉及到实数连续统的极为深刻的知识。因此我们只要接受它作为一个已知事实即可。对于a的取值为非零有理数，有必要分成几种情况来讨论各自的特性：首先我们知道如果a=p/q，q和p都是整数，则x^(p/q)=q次根号（x的p次方），如果q是奇数，函数的定义域是R，如果q是偶数，函数的定义域是[0,＋∞）。当指数n是负整数时，设a=-k，则x=1/(x^k)，显然x≠0，函数的定义域是（－∞，0)∪(0,＋∞).因此可以看到x所受到的限制来源于两点，一是有可能作为分母而不能是0，一是有可能在偶数次的根号下而不能为负数，那么我们就可以知道：排除了为0与负数两种可能，即对于x>0，则a可以是任意实数；排除了为0这种可能，即对于x<0和x>0的所有实数，q不能是偶数；排除了为负数这种可能，即对于x为大于且等于0的所有实数，a就不能是负数。总结起来，就可以得到当a为不同的数值时，幂函数的定义域的不同情况如下：如果a为任意实数，则函数的定义域为大于0的所有实数；如果a为负数，则x肯定不能为0，不过这时函数的定义域还必须根据q的奇偶性来确定，即如果同时q为偶数，则x不能小于0，这时函数的定义域为大于0的所有实数；如果同时q为奇数，则函数的定义域为不等于0 的所有实数。在x大于0时，函数的值域总是大于0的实数。在x小于0时，则只有同时q为奇数，函数的值域为非零的实数。而只有a为正数，0才进入函数的值域。由于x大于0是对a的任意取值都有意义的，因此下面给出幂函数在第一象限的各自情况.可以看到：（1）所有的图形都通过（1，1）这点。（2）当a大于0时，幂函数为单调递增的，而a小于0时，幂函数为单调递减函数。（3）当a大于1时，幂函数图形下凹；当a小于1大于0时，幂函数图形上凸。（4）当a小于0时，a越小，图形倾斜程度越大。（5）a大于0，函数过（0，0）；a小于0，函数不过（0，0）点。（6）显然幂函数无界。 [编辑本段]高斯函数设x∈R ， 用 [x]或int(x)表示不超过x 的最大整数，并用表示x的非负纯小数,则 y= [x] 称为高斯（Guass）函数，也叫取整函数。任意一个实数都能写成整数与非负纯小数之和，即：x= [x] + （0≤<1） [编辑本段]复变函数复变函数是定义域为复数集合的函数。复数的概念起源于求方程的根，在二次、三次代数方程的求根中就出现了负数开平方的情况。在很长时间里，人们对这类数不能理解。但随着数学的发展，这类数的重要性就日益显现出来。复数的一般形式是：a+bi，其中i是虚数单位。以复数作为自变量的函数就叫做复变函数，而与之相关的理论就是复变函数论。解析函数是复变函数中一类具有解析性质的函数，复变函数论主要就研究复数域上的解析函数，因此通常也称复变函数论为解析函数论。复变函数论的发展简况复变函数论产生于十八世纪。1774年，欧拉在他的一篇论文中考虑了由复变函数的积分导出的两个方程。而比他更早时，法国数学家达朗贝尔在他的关于流体力学的论文中，就已经得到了它们。因此，后来人们提到这两个方程，把它们叫做“达朗贝尔-欧拉方程”。到了十九世纪，上述两个方程在柯西和黎曼研究流体力学时，作了更详细的研究，所以这两个方程也被叫做“柯西-黎曼条件”。复变函数论的全面发展是在十九世纪，就像微积分的直接扩展统治了十八世纪的数学那样，复变函数这个新的分支统治了十九世纪的数学。当时的数学家公认复变函数论是最丰饶的数学分支，并且称为这个世纪的数学享受，也有人称赞它是抽象科学中最和谐的理论之一。为复变函数论的创建做了最早期工作的是欧拉、达朗贝尔，法国的拉普拉斯也随后研究过复变函数的积分，他们都是创建这门学科的先驱。后来为这门学科的发展作了大量奠基工作的要算是柯西、黎曼和德国数学家维尔斯特拉斯。二十世纪初，复变函数论又有了很大的进展，维尔斯特拉斯的学生，瑞典数学家列夫勒、法国数学家彭加勒、阿达玛等都作了大量的研究工作，开拓了复变函数论更广阔的研究领域，为这门学科的发展做出了贡献。复变函数论在应用方面，涉及的面很广，有很多复杂的计算都是用它来解决的。比如物理学上有很多不同的稳定平面场，所谓场就是每点对应有物理量的一个区域，对它们的计算就是通过复变函数来解决的。比如俄国的茹柯夫斯基在设计飞机的时候，就用复变函数论解决了飞机机翼的结构问题，他在运用复变函数论解决流体力学和航空力学方面的问题上也做出了贡献。复变函数论不但在其他学科得到了广泛的应用，而且在数学领域的许多分支也都应用了它的理论。它已经深入到微分方程、积分方程、概率论和数论等学科，对它们的发展很有影响。复变函数论的内容复变函数论主要包括单值解析函数理论、黎曼曲面理论、几何函数论、留数理论、广义解析函数等方面的内容。如果当函数的变量取某一定值的时候，函数就有一个唯一确定的值，那么这个函数解就叫做单值解析函数，多项式就是这样的函数。复变函数也研究多值函数，黎曼曲面理论是研究多值函数的主要工具。由许多层面安放在一起而构成的一种曲面叫做黎曼曲面。利用这种曲面，可以使多值函数的单值枝和枝点概念在几何上有非常直观的表示和说明。对于某一个多值函数，如果能作出它的黎曼曲面，那么，函数在离曼曲面上就变成单值函数。黎曼曲面理论是复变函数域和几何间的一座桥梁，能够使我们把比较深奥的函数的解析性质和几何联系起来。近来，关于黎曼曲面的研究还对另一门数学分支拓扑学有比较大的影响，逐渐地趋向于讨论它的拓扑性质。复变函数论中用几何方法来说明、解决问题的内容，一般叫做几何函数论，复变函数可以通过共形映象理论为它的性质提供几何说明。导数处处不是零的解析函数所实现的映像就都是共形映象，共形映像也叫做保角变换。共形映象在流体力学、空气动力学、弹性理论、静电场理论等方面都得到了广泛的应用。留数理论是复变函数论中一个重要的理论。留数也叫做残数，它的定义比较复杂。应用留数理论对于复变函数积分的计算比起线积分计算方便。计算实变函数定积分，可以化为复变函数沿闭回路曲线的积分后，再用留数基本定理化为被积分函数在闭合回路曲线内部孤立奇点上求留数的计算，当奇点是极点的时候，计算更加简洁。把单值解析函数的一些条件适当地改变和补充，以满足实际研究工作的需要，这种经过改变的解析函数叫做广义解析函数。广义解析函数所代表的几何图形的变化叫做拟保角变换。解析函数的一些基本性质，只要稍加改变后，同样适用于广义解析函数。广义解析函数的应用范围很广泛，不但应用在流体力学的研究方面，而且象薄壳理论这样的固体力学部门也在应用。因此，近年来这方面的理论发展十分迅速。从柯西算起，复变函数论已有170多年的历史了。它以其完美的理论与精湛的技巧成为数学的一个重要组成部分。它曾经推动过一些学科的发展，并且常常作为一个有力的工具被应用在实际问题中，它的基础内容已成为理工科很多专业的必修课程。现在，复变函数论中仍然有不少尚待研究的课题，所以它将继续向前发展，并将取得更多应用。 upcase 字符型 使小写英文字母变为大写 字符型 downcase 字符型 使大写英文字母变为小写 字符型 [编辑本段]阶梯函数形如阶梯的具有无穷多个跳跃间断点的函数. [编辑本段]反比例函数表达式为 y＝k／x(k为常数且k≠0) 的函数，叫做反比例函数。反比例函数的其他形式：y=k/x=k·1/x=kx-1反比例函数的特点：y=k/x→xy=k自变量x的取值范围是不等于0的一切实数。反比例函数图像性质：反比例函数的图像为双曲线。反比例函数关于原点中心对称，关于坐标轴角平分线轴对称，另外，从反比例函数的解析式可以得出，在反比例函数的图像上任取一点，向两个坐标轴作垂线，这点、两个垂足及原点所围成的矩形面积是定值，为∣k∣,即k的绝对值。如图，上面给出了k分别为正和负（2和-2）时的函数图像。当 k >0时，反比例函数图像经过一，三象限，因为在同一支反比例函数图像上，y随x的增大而减小所以又称为减函数当k <0时，反比例函数图像经过二，四象限，因为在同一支反比例函数图像上，y随x的增大而增大所以又称为增函数倘若不在同一象限，则刚好相反。由于反比例函数的自变量和因变量都不能为0，所以图像只能无限向坐标轴靠近，无法和坐标轴相交。 知识点：1.过反比例函数图象上任意一点作两坐标轴的垂线段，这两条垂线段与坐标轴围成的矩形的面积为| k |。2.对于双曲线y＝ k/x，若在分母上加减任意一个实数m (即 y＝k／x（x±m）m为常数)，就相当于将双曲线图象向左或右平移m个单位。（加一个数时向左平移，减一个数时向右平移） [编辑本段]程序设计中的函数许多程序设计语言中，可以将一段经常需要使用的代码封装起来，在需要使用时可以直接调用，这就是程序中的函数。比如在C语言中:int max(int x,int y){return(x>y?x:y;);}就是一段比较两数大小的函数，函数有参数与返回值。C++程序设计中的函数可以分为两类：带参数的函数和不带参数的函数。这两种参数的声明、定义也不一样。带有（一个）参数的函数的声明：类型名标示符+函数名+（类型标示符+参数）{}不带参数的函数的声明：void+函数名（）{}花括号内为函数体。带参数的函数有返回值，不带参数的没有返回值。C++中函数的调用：函数必须声明后才可以被调用。调用格式为：函数名（实参）调用时函数名后的小括号中的实参必须和声明函数时的函数括号中的形参个数相同。有返回值的函数可以进行计算，也可以做为右值进行赋值。#include using namespace std;int f1(int x, inty){int z;
return x+y;
}void main(){cout<}C语言中的部分函数main（主函数）max（求最大数的函数）scanf（输入函数）printf（输出函数）

历史表明，重要数学概念对数学发展的作用是不可估量的，函数概念对数学发展的影响，可以说是贯穿古今、旷日持久、作用非凡，回顾函数概念的历史发展，看一看函数概念不断被精炼、深化、丰富的历史过程，是一件十分有益的事情，它不仅有助于我们提高对函数概念来龙去脉认识的清晰度，而且更能帮助我们领悟数学概念对数学发展，数学学习的巨大作用． （一） ��马克思曾经认为，函数概念来源于代数学中不定方程的研究．由于罗马时代的丢番图对不定方程已有相当研究，所以函数概念至少在那时已经萌芽． ��自哥白尼的天文学革命以后，运动就成了文艺复兴时期科学家共同感兴趣的问题，人们在思索：既然地球不是宇宙中心，它本身又有自转和公转，那么下降的物体为什么不发生偏斜而还要垂直下落到地球上?行星运行的轨道是椭圆，原理是什么?还有，研究在地球表面上抛射物体的路线、射程和所能达到的高度，以及炮弹速度对于高度和射程的影响等问题，既是科学家的力图解决的问题，也是军事家要求解决的问题，函数概念就是从运动的研究中引申出的一个数学概念，这是函数概念的力学来源． （二） ��早在函数概念尚未明确提出以前，数学家已经接触并研究了不少具体的函数，比如对数函数、三角函数、双曲函数等等．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的函数．在此定义中，已在形式上回避了“对应”的术语，全部使用集合论的语言了． ��从以上函数概念发展的全过程中，我们体会到，联系实际、联系大量数学素材，研究、发掘、拓广数学概念的内涵是何等重要．

反编译在航天工业中的应用*赵 蕾 吴 岩 王开铸(哈尔滨工业大学计算机系319信箱*哈尔滨*150001) 摘 要 本文论述了反编译作为一种程序验证的工具在航天工业中的重要地位和应用;介绍了反编译的背景知识;给出一个实用的反编译系统DCPL的设计模型和关键技术及其一个运行结果示例以说明反编译器的功能。 主题词 反编译 软件工具 程序验证 程序可靠性APPLICATION OF DECOMPILATION TO AEROSPACE INDUSTRYZhao 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 reliability1 引 言 航天工业是各国竞相发展的一项事业。航天器的各部分都离不开计算机的控制,各种控制软件、计算软件、分析软件等等在航天器的设计与应用中起着重要地位。 1996年6月4日阿里亚娜-5型火箭发射失事,使欧共体蒙受25亿美元以上的损失。经过专家调查,此次失事的主要原因是:箭载计算机系统使用的软件出了问题。此软件是从阿里亚娜-4型火箭的软件系统中移植过来的,由于5型火箭上增加了新机构,而4型火箭的软件不能对这些新机构发出的信号进行分析和处理,从而导致火箭控制失灵。由于阿里亚娜-5型火箭发射的失事,使软件可靠性和正确性问题再度摆到软件开发者面前〔1〕。反编译器作为一种有效的程序验证的工具使人们再度意识到它在航天工业中的重要性及实用性。本文介绍了反编译器的功能、产生背景和它在航天工业中的应用,并给出了我们正在研制的一个实用反编译系统DCPL的体系结构及关键技术,最后给出其一个简单的运行示例。2 反编译的背景知识介绍 反编译的定义 反编译可以看成是编译的逆过程,即将以机器语言形式存在的目标代码翻译成与其功能等价的高级语言形式的代码的过程〔2〕。 确定型反编译的模型为一个映射,decompile:S—＞T,其中S是源代码集(source),是机器指令集;T是目标代码集(target),是高级语句集。 反编译的产生背景 反编译(Decompilation)一词第一次出现于1960年。六十年代,随着第三代计算机的产生,为了挽救大量的运行在即将报废的第二代计算机上的软年,同时也为加速开发第三代机器的软件,美国开始研制专门用途的反编译器作为软件移植的工具。 反编译在航天技术中的应用 反编译发展至今,其应用领域主要体现在软件维护和软件安全性〔2〕两方面。用于软件维护时,主要是恢复丢失的源代码、将软件移植到新的硬件平台、重新结构化旧有软件等等。用于软件安全性时,主要是针对安全性要求极高(safty-critical)的软件,发现其中是否有病毒,或是否有隐藏的窃密程序(Trojan)。 西方各国早已将反编译技术用于航天事业和尖端工业,如:IBM为NASA的航天飞机研制的反编译器〔3〕;澳大利亚电子研究实验室研制的针对类Pascal语言的反编译器〔4〕;欧共体ESPRIT计划中的反编译研究,如英国的核工业部使用反编译技术验证大量的safty-critical软件,以提高软件的正确性〔5〕;我国从80年代初开始反编译的研究并且已逐步形成自己的产品〔6〕,但尚未见将反编译技术应用于航天技术的报导。 用于航天的软件系统通常不经过编译优化以避免不必要的软件错误,反编译此类软件的难度相对减小。可以通过将内存映象的反编译结果与原始输入(源程序)相比较来验证软件的正确性,如果二程序完全等价,则编译结果可靠(反编译可靠的前提下)。如下图示:图1 反编译验证程序正确性如果对于每一种输入,都有输出1=输出2=预测结果,则可说明编译是可靠的。同样也可通过比较原始程序和反编译结果在程序功能空间中的拓朴结构是否完全一样,来判定反编译是否做到了输出结果与原始程序功能等价,这通常要经过大量的测试。3 一个实用反编译系统DCPL的体系结构 DCPL是我们研制的一个反编译系统,其设计吸收了编译技术中的成熟理论。 DCPL体系结构 下图给出了DCPL的模型。它以可执行文件作为输入,输出与其对应的C语言程序。图2 DCPL体系结构 DCPL各模块的功能 (1)预处理器:是DCPL的基础,以可执行文件作为输入,将其部分反汇编,根据程序的启动代码,提取出相应的数据段和代码段,存储在中间文件中。 (2)库函数识别器:是对中间文件的一遍扫描。根据库函数特征表识别出文件中所有库函数和用户自定义函数的入口。采用顺序-索引-连接技术构造特征表。索引函数的形式为:index(len,n)=w1*len+w2*n;其中len和n分别为函数主体的长度和它所调用辅函数的次数。用一指针数组指向各个特征链的头结点,数组的下标值是索引函数作用于各个特征结点上的结果;同一个链上的各个结点的特征值经索引函数作用后其值相同;链表内部,各结点依照使用频率顺序存放。 (3)控制流分析器:根据反编译控制流文法,以语法制导的方法进行控制流的分析和归约,生成控制流模块的机内表示形式及其结构文件。采用约束属性文法描述控制流,如∷=jmp{statement}m0{cmp}｜｜之后的是该规则的约束。用移进-归约策略和模式匹配方法相结合进行分析和归约。 (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语言程序形式,输出给用户,完成反编译的任务。 系统的一个运行结果举例 下面是一个简单的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 BP2386:01FD 8BECMOVBP,SP2386:01FD 83EC02SUBSPM+022386:0200 56PUSHSI2386:0201 57PUSHDI2386:0202 8D46FELEAAX,〔BP-02〕2386:0205 50PUSHAX2386:0206 B89401MOVAX,01942386:0209 50PUSHAX2386:020A E86714CALL16742386:020D 59POPCX2386:020E 59POPCX2386:020F 837EFE00CMPWORD PTR〔BP-02〕,+002386:0213 7C14JL02292386:0215 837EFE14CMPWORD PTR〔BP-02〕,+142386:0219 7E09JLE02242386:021B 8B7EFEMOVDI,〔BP-02〕2386:021E 8BF7MOVSI,DI2386:0220 46INCSI2386:0221 46INCSI2386:0222 EB03JMP02272386:0224 8B76FEMOVSI,〔BP-02〕2386:0227 EB0AJMP02332386:0229 8B76FEMOVSI,〔BP-02〕2386:022C 8BC6MOVAX,SI2386:022E F766FEMULWORD PTR〔BP-02〕2386:0231 8BF8MOVDI,AX2386:0233 56PUSHSI2386:0234 B89701MOVAX,01972386:0237 50PUSHAX2386:0238 E8990BCALL0DD42386:023B 59POPCX2386:023C 59POPCX2386:020D 5FPOPDI2386:020E 5EPOPSI2386:023F 8BE5MOVSP,BP2386:0241 5DPOPBP2386:0242 C3RET4 结束语 发展航天事业是我国的一项国策,航天计划的成功完成是众望所向。近几年各国因航天器的软件可靠性较差导致的种种航天发射失败所造成的不必要的人员伤亡和财政浪费,使得软件正确性验证日益显现出重要性。反编译正是解决这一课题的极佳工具。我国在该课题上的研究尽管起步较国外晚,但现已取得了长足的进展。经济国内反编译同行的研究和实践,现有的反编译系统基本达到了验证简单程序的要求,但要反编译大规模的软件,诸如用于航天计划中的软件,还需要深入的研究。将反编译技术应用于航天领域以提高航天器材的可靠性,航天发射的成功率,航天器运行的正确性,确实是一个很有前途的研究方向。参考文献1 李未.欧洲程序设计方法研究的三个动向.智能机研研究动态,Vol 9,19962 Cristina Cifuentes and John Gough of binary Practice and Experience,1995,25(7)3 Spector A and Gifford study:the space shuttle primary computer system,Communications of the ACM,27,872-9004 Hood S with definite clause Report,ERL-0571-RR,19915 Pavey D J and Winsborrow L equivalence of source code and PROM European Workshop on Dependable Commputing,8-10,19926 合肥工业大学微机所.DECLER用户使用手册.