论文研究-基于H-等价的算法识别技术研究.pdf

所需积分/C币:5 2019-09-07 18:12:16 745KB .PDF

蕴涵在程序代码中的语义是程序语言词法和语法的抽象表达,构成了人脑思维与机器思维交互过程的中间变换。从指称语义出发,结合具体语言,用形式化的方法讨论了语义等价和H-等价(Herbrand等价)。H-等价的判定条件相对来说更容易得到满足,具有更广泛的可用性。结合具体算法给出了H-等价在算法识别方面的应用成果及其局限性。
762007,43(3) Computer Engineering and Applications计算机工程与应用 EHI I Ooh (NI C,I, C, O) sum_a=a(o); slm(0)=a(0); Ooh. (B ,c() sum b=b(o) sLm(n+1)=b(0) EHlo AOOH.((1),a(v)) while(i<n) while(i<n) EHI(erer)I OoH =(FI I(En I er l ooH. I ek I ooH) Isum_=sum_ata(i) Sum(i)=sum(i-1)+a(i) A e leIl P v=e -AoTH (olei|], oHEi/ul) + PHIS2l。PhtS1 eturn sum a+sum b return sum(n)+sum(2*n+1) PH I if C S, else S2 =AooH(E,IC IooH PHI S, I oOH PHI S2] ooH PHI while C S =Agom(,I COoh (b(0)+…)+b(n) (b(0)+…)+b(n (PH I while C oPHI S)ooH (A1)原始程序 (A3)数据结构变形 图2H-扩充指称语义 sum_a=a(o) nt i=0: 注:TA(D)为数组时,其第i项表示为T(D)i while(i<n-2) H-等价定义如下 I sum_a=sum_ata(i) 定义2H-等价。算法A1和算法A2是H-等价的,记作 sum a=sum ata(itl); A1≡HA2,当且仅当 sum b=b(o) (1)或者A1和A2都不终止; f(l=n/2) (2)或者A1和A2都终止,且输出相同的计算项,即对每 while(i<n) sum a=sum ata(n) 个 sum b=b(o) T41(D)i=TA2(1)[ sum_b=temp+b(i) H-等价定义说明,如果AI和A2执行的计算项相同,则 garbage=garbage+I hile (i<n= 它们是H-等价的。文献[2]证明,H-等价是比语义等价更弱的 sum a=sum a+a(i) [sum_b=sum_b+b(i) 程序等价关系。即 A1≡HA2→A1≡A2 return sum atsum b: retrun sum a+sum b; II-等价比语义等价弱,其等价类是后者等价类的子集,但 (a(0)+…)+a(n)+ (a(0)+…)+a(n)+ 是包含了保持计算项不变条件下的所有的程序变换,可以用 (b(0)+…)+b(n) (b(0)+…)+b(n) H-等价来判定许多程序变体之间的等价问题。 (A2)组织结构变形 (A4)控制结构变形 4算法识别应用 的等价,在定义中并没有考虑运算符的性质,所以不能用来判 算法识别技术要解决的主要难点是如何识别程序代码的定由于运算符性质引起的语义变形程序之间等价问题。例如加 多样化问题。一般将代码的多样化分为如下四类 法运算符具有可结合性和可交换性,得到算法A1的计算项为 (1)组织结构多样化:相互无依赖关系的语句位置变更与 T41(a)=a(0)+a(1)+…+a(9)+a(10) 局部变量的引入造成了结构多样化。如切片A2所示 A2的计算项为 (2)数据结构多样化:同样的计算可以采用不同的数据结 T42(a)=a(10)+a(9)+…+a(1)+a(0) 构,造成了数据结构多样化。如切片A3所示。 实际上算法A1和A2是语义等价的,而根据H-等价的定 (3)控制多样化:控制结构的变形造成了控制多样化,顺文,结果判定为:A1≠μ:A2 序、选择、循环这三种基本结构的实现方法有时可以相互替代, 切片A4展示了一个算法的结构变形。 5结束语 (4)语义多样化:由运算符性质导致的程序变形造成了语 由于程序设计话言表示的多样化,算法的实现往往呈现出 义多样化。例如下文交待的运算符“+”具有可交换性,运用该不同的语法形态,特别是程序可以采用加扰等手段来改变其语 性质可以导致目标程序实现的不同。 法形态。归根结底,程序是否等价取决于程序是否具有相同的 由于采用不同的组织结构、数据结构、控制结构和语义结语义,对程序等价问題的研究往往需要借助形式分析的手段。 构变形,同一算法的程序实现可以表现为不同形式。目前已有 本文从指称语义出发,结合具体语言,讨论了程序的语义 的算法识别方法大都基于文法层次的匹配,只能识别一些组及语义等价的定义,研究了H等价的定义和性质。H-等价是 织结构变形,然而算法具体实现过程中,程序代码的数据结构比语义等价更弱的程序等价关系,可以来判定组织结构数据 和控制结构的变形经常发生。除了语义多样化,H-等价可以来结构和控制变形程序之间的等价问题。然后,通过具体算法的 判定组织结构、数据结构和控制变形程序之间的等价问题 例子给出了H-等价在算法识别方面的应用成果,并分析了H- 举例如下,两数组求和算法可以有以下四种不同形式,如等价应用的局限性:不能识别程序的语义多样化变形 下所示。采用基于H-等价的判定方法,可以得到它们的计算项 程序等价问题历来是计算机科学领域备受关注的研究课 相同,所以:A1≡日A2≡1A3≡1A4 题,不仅应用于软件逆向工程和程序理解,在编译优化、程序验 H-等价不能识别所有程序代码的多样化问题,其应用仍证等领域也有非常重要的应用。(收稿日期:2006年9月) 然存在局限性。H-等价通过对计算项的形式比较来判定程序 (下转83页)

...展开详情
试读 3P 论文研究-基于H-等价的算法识别技术研究.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于H-等价的算法识别技术研究.pdf 5积分/C币 立即下载
    1/3
    论文研究-基于H-等价的算法识别技术研究.pdf第1页

    试读已结束,剩余2页未读...

    5积分/C币 立即下载 >