论文研究-基于依赖的污点分析方法改进研究.pdf

所需积分/C币:39 2019-07-22 22:18:48 969KB .PDF
收藏 收藏
举报

在总结污点分析研究现状基础上,给出了基于依赖的静态污点分析的形式化描述。提出并形式化定义跨方法的域变量和方法参数变量依赖关系以及依赖关系传播的操作语义,改进分析的精度。引入迭代求精方法对分析结果进行多阶段和验证,改进分析的性能。在SOOT平台实现改进分析的原型系统并与现有分析比较,实验结果表明改进方案有效提高了精度和性能。
第10期 郭帆,等:基于依赖的污点分析方法改进研究 3067 本文以SOOT平台下 Jimple语言(一种中间代码)的子集Jm ∪:VP1,P2∈8, ple_S为目标语言,对CI方法进行形式化描述。 1)(l1,t),l)∈P1A-3l(l1,),L)∈p23(l1,),L2)∈ 2.2.1 Jimple_s的抽象文法 算法1给出 Jimple_S的抽象文法。 Jimple_S是 Jimple语 2)(4,2),L1)∈P1A((1,n),L1)EP2→((41,),L1UL1)∈ 言的」集,仅包含垗转赋值、方法调用和返叫语句。 1, assion_s 3)((l2,x),L2)cp2A-彐r.(l2,n),L,)cP1→((l,n),L)c 表示方法的入口赋值语句,用于将形参的第i个参数@para_i Cx: (C, ce) Ux:(U, U6) 或者方法调用对象@this映射为方法内部定义的局部变量2.2.3依赖关系的形式化定义 (id)。方法调用语句支持Java宇节码规范屮静态方法和实例 CI分析依赖两项预先计算结果,包括:a)程序的指针分柝 方法凋用。 Jimple规范约定赋值语句的左右操作数中堆对象结果,指明每个变量v(包括堆变量)可能指向的内存空间集合 访问(a订或a.至多出现一次。从 assign_s和 ret ret_v语句PA(v),木文引用的指针分析是CI和流不敏感的指针分析;b 的定义可以看出, Jimple_S程序对变量的赋值只包含宇符串常CI方法调用图,用于形式描述方法调用入口和返回语句的操 量,不存在整型等标量类型,即 Jimple_s仅关心Java对象的语作语义。假设分析已经建立了指针分析结果PA:v→P(Al- 义,其他标量变量类型被忽略。由于分析并不关系对象的具体 loc set), Allose指称系统中所有堆分配的内存地址集合,已经 类型, Jimple表达式中的类犁转换也在 Jimple s中被忽略。建立跨方法的控制流图(CHG),已经建立基于PA的系统方法 Jimple_s屮的跳转语句在分析屮主要用于建立控制流图,此类调用图CG。 语句未定义任何变量。 定义1s和t为同一方法内两条不同语句,数据依赖关 算法1 Jimple_S的抽象文法 系s→→t成立当且仅当 P: goto labelI if b exp r go to label I assign_s )v∈Uses(s)∧ I invoke s I i assign sI retret v I return invokes:= invoke_exp r b)彐u∈Defs(t),PA(u)∩PA(v)≠A dssign s:=var e)s,…,s,i=0,…,n-1,Vi,S→S1+1∈Flow(CFG), ke expl rI va So=s,Sn=,j∈1,…,n-1,∈De(s) invoke_exp r:= invoke_key id. meth( arg,, .. arg Uses(s)和Des(s)分别表示语句s中使用和修改的变量 oke meth( 集合,Fow(CFG)表示该方法CFG的边集合。该定义与文 I 'virtual invoke [28的直接依赖关系不同,只要路径中不存在对变量v的直接 var:= id I idid I idl _i I id. id 修收,且目标语句修改的变量u与v可能指向同个内存位 ret v:=id es argi.=idic ilc s 置,则认为两条语句之间存在依赖关系。这里的t和t是局部 bexpr:= var binp id I id binp var? I unop var 对象变量,而不是堆变量。 c_i: interger const c s: string const id identifier binp: binary at 定义2s和t是程序內任意两条语句,数据依赖关 Inop: unary arithmatic opeator .idt成立当且仅当 2.2.2 Simle_S程序的抽象状态空间 a)v.id∈Uses(s)∧ 定义抽象状态空间Σ=(P(N),),N是与初始变量集合 b)彐u.id∈nefs(t),PA(u)∩P4(v)≠ N有依赖关系的节点集合,节点由(l,)表示,指称语句l的变 定义3s和t是程序内任意两条语句,数据依赖关系s→n 量t;表示每个节点所依赖的语句集合,指称语句的变量[id]t成立当且仅当 (堆变量和局部对象变量)映射到其直接依赖的语句集合。N a)[id]∈Uscs(s)∧ 在初始化时手工确定,由语句标签和变量的符号表示(l,v) b)彐u[id.∈Dfe(t),PA(u)∩P(u)≠Q 确定。Ln集合表示程序P的所有语句集合,L表示语句集合 定义2、3定义数组元素访问和对象域访问的依赖关系,它 V表小程序p中所有出现的变量集合 们是跨方法的,并且不需要在ICFG中存在访问路径,即对于 算法2给出形式化定义状态空间Σ、最小元素∑、最大元语句a=t.id,它的依赖语句集合是所有类似u.id=b的语句, 素E、包含关系Cx和合并关系∪s。依据关系算子Cp的定其中t和u可能指向同一个内存位置。数组元素访间类似,仅 义,P1三gP2等价于对于任意节点(l,)其在P;中指向的语句考虑数组对象自身的指针分析结果,而不考虑数组元素下标 集合L,必然有在语句集合L包含L,且(l,)在P2屮指向L。即对丁同一数组的任何不同元素访问都认为是相同的 容易证明其白反性、反对称性和传递性,即可证明(Σ,x)为 定义4为id=@para_i,数据依赖关系s→c,arg;t成立 偏序集合。根据合并关系∪3以及包含关系三、的定义,容易当仅当t为: 证明V∑,∑2∈∑,1C:S1∪x2∧∑2CxS1U2∑2且∑存在最 a )id= id,. meth( arg,, ..,arg.)V id meth (arg,, .,arg.) 大和最小元素,容易构造一条有限递增链Σ,因此抽象状态空 id1.meth(arg1,…,argn)mcth(arg,…,argn))∧ 间(Σ,Σ,x,ss,∪x)构成完各格。 b)t∈ callsites(meth)∧s∈Ln 算法2程序的扯象状态空间 定义5为id=id1,meth(arg,…,argn)Vid=meth l: label of statements L,: all labels of program(p) L:i lI set of labels v,: varI all var s in program(p) (arg1,…,argn),数据依赖关系s→,id成立当且仅当 2:(P(N),8)∑b=(N,)∑t=(N,1) a)为 ret ret 2∧ N:i (L, var)IN,=N,=I(L,u)Ilc Lo, vcv b)s∈ca th)A :P(NP({ll-p))==((l,n),L)(1,u)N2 C;VP1,P2∈8),P1SP2÷V(l1,t),L· 定义45中的L指称方法meth中的语句集合,而cl (l1,n),L)∈p1→1l,LsLA((l,n),L)∈P2 siLes(meth)指称方法调用图CG中所有可能调用melh的语句 3068· 计算机应用研究 第33卷 集合。定义4形式化描述形参到实参的依赖关系,每种方法的l) 形参与所有可能调用该方法的实参均有依赖关系,t枚举了 10)id,. meth( arg argn )Uses = id,, argI, -. argn I Defs=0 词用方法的每个可能返回值,也依赖于不同调用方法的不同返分sUe(),f(t,)∈NY(,,,1)ePe(4) Jimple_S中所有可能的调用语句类型(参见图3)。定义5形 式化描述从方法调用返回时,实际的返回值既依赖于同一种被 1)|3)‖5)6)→N:=N+(l,Uses(l4),P1=p;+(l,t, l2=8)|9)→N=NU|(l,n1)1"1+Defs(la),p1=p;+(l,t 回值。 2.2.4漠作语义 11)mcth(arg1,…,argn)Uses={arg1,…,argn}Dcfs=N=N。 从 Jimple s程序牛成依赖图的操作语义(转换函数)如算 Yr∈Uses(l,),if(,")∈N。,V(l,t,l,1)∈Prev(l,) 法3所示。所有影响变量状态的 Jimple_S语句分为11种。 l2∈1)|3)‖5) (Li, Uses(l,) ), Pi =p+( 定义1~5形式化描述了CI分析屮的直接依赖关系。假设存 在依赖图G,包含程序P中每条语句的直接依赖边,每条边由分8)19)→M=NU1(4,n)=Des(4),P=P+(1,n 定义1~5的形式定义,G的节点是程序P中的语句。Prev(l,) 采用后向数据流分析,分析语句前的状态是 Analysis(l)= 指称节点l在G中的边集合,edge(l,x,la,l)表示一条依赖=(N,p),经过转换函数后 Analysis(l)=X=(N,p),算 边,t表示依赖类型(定义1~5),4指称目标语句,变量指称法3中每条语句的转换函数/,则有(N,P)=1(N2,n)。C 1、中使用的变量可能被l修改。 分析可形式化描述为 算法3 Jimple_S的操作语义 Analysis; l)=i( Analysis, (4)) I)id =id, Uses= id,, Defs=iid N,=N, P:=p Analysis()=∪x{ Analysis(1)|l∈Pev(l1) if(l,id2)∈N。,H(l,,id2,la,1)∈nrev(l,) 根据 Tarski不动点定理,由于扯象状杰空间是完备格, 1)|3)5)16)→N2=N2+(l,Ue(t4),p1=p1+(,12,该分析必然会迭代至不动点,此时的抽象状态即为与输人语句 4)∈8)∥/9)→N1=NU(l,n)∈Des(12)),P=P+(,过2,变量对(l,)可能有依赖关系的语句变量对集合N以及依 2)id,id 2=id, Ises= itl!, Defs=fid,id2, N;=N, Pi=p 赖边集合P(nc f(l,id3)=N,Ⅴ(!,idl3,la,1)∈Prev(l) 语句1)2)4)7)的转换函数语义相同,它们只有类型1的 a-1)‖3)‖5)|6)→N:=N+(la,Uses(l)),P;=pz+(l,id3 la 依赖边,因为它们的Uses集合只有一个变量,且该变量是局部 fs(1g)), p 对象变量,不是数组元素访问和对象域访问,即对象变量(lo- la al)只与 local有直接依赖关系,不与堆变量发生直接依赖关 3)id, =id. id, Uses=| id. id,I, Defs=id3I N, =N, Pi=p V(l、,idt.id2,l4,2)∈Prev(l,) 系,它们之间的依赖关系只能间接地通过赋值语句生成 L, c2)N,=N,+(L,, Use(L,)),P, =,+(ls, id. id,, l,) 当目标诘句l是方法调用吋,把方法调用的返回值加入 id id1」}N;=N 集合N。因为返叫值与被调用方法的返回语句之间存在隐含 !∈1)‖3)‖5)|6)N;=N;+(la,Uses(l)),p;=p;+(l 的形参实参赋值语句,即(la,id)实际上依赖于被调用方法的 l !∈8)‖9)→N;=NU(l4,t)|t∈Defs(l4)),P:=p;+(l1 返回语句中的rett变量。 L,) 语句3)5)的转换函数语义类似,分别只有类型2和3的 5)id,id[ id, Uses= id[id, 1i, Defs=:id, N, =N,, P, =p 依赖边,辶们分别只与对象域访问和数组元素访冋有直接依赖 (la, Use(L,)), Pi=Pi+(ls, id[ id, I d) 关系 6)id=(@ para Uses=1(@ para!, Defs=i id! N, =N,, p:=p 语句6)的转换函数处理方法调用语义,方法调用时由隐 if(Is, para)=N,, V(L,, para, I 4)E Prev(1,) 4c8)|9)‖10)‖11)→N2=N;+(la,arg;),P1=P;+(l,@para, 含的赋值语句将实参赋予形参,@para指称第i个形参,则arg, 指称调用语句处的第i个实参。根据Prev(l、)和直接依赖关系 7 )ret ret_v Lses =|ret_e N,=N,, P, =p f(,rett)∈N。,(l,,ret,l4,1)∈Prev(l) 的定义,这里的调用语句集合为 callsites(meth),meth为l所 4∈1)‖3)‖5)|6)→N1=N2+(la,Uses(4),P1=P1+(l,ret在方法。 ∈8)‖9)→N;=N2U{(l4、n)∈Des(l4)),F2=p2+(l 语句8)9)的转换函数语义相同,其共Prev()集合有两种 直接依赖边:a)类型5的边,从调用语句l、连接被调用方法的 8)l-dmr(ay,…,apn)Ues=id,a,…, argn Defs=返回语句l,Ue(1)为{rex},此时仅需要(l,et)加入N ,P1=P if(l,id)∈N。,V(l,,id,la,5)∈Prev(l, b)类型1的边,这时与语句1)的谙义相似,区别在丁并不是 4∈7)→N1=N+(la,Uses(l),P1=P1+(l、,id,l) Use集合中所有的参数都会进行计算,而是计算有依赖关系的 ∈1)13)15)16)→N1=N,+(1,1=(),1=1+(1,n,参数,即参数必须属于N。语句6)8)9)结合在一起构成了跨 方法的间接依赖数据流 !∈8)‖9)→N;=N;U|(la,1)t1∈Dfs(la)),p2=p;+(l,t la) 10)11)的转换函薮语义相同,与语句8)的转换数相比 9)id meth( arg arg Defs=iid M 少了类型5的边,即它们使用类似语句1)的语义进行处理 ,P:=P0 if(l,id)∈N。,Y(l,id,l1,5)∈Prev() 从算法屮可以看出,语句10和11只能通过方法的入口语句依 7)-N=N;+(Ia, Uses(l,) (l,,id,l4) 赖关系而来,因为它们的Def集合为空集,所以不存在目标语 V vc Uses(l2),道(l、,t)cNn,V(l、,t,4,1) c Prey(l、) 句为10)11)的类型1的边 !∈1)‖3)‖5)|6)→N;=N,+(la,Uscs(la)),p;=p;+(l,,U, lai 对于方法内代码无法访问的情形,将此类方法调用语句使 !4∈8)‖9)→N;=N;U{(la,n)t1∈Defs(la)),D2=p;+(l 用类型12~15表示,如算法4所示 第10期 郭帆,等:基于依赖的污点分析方法改进研究 3069 算法4 Native方法操作语义 20 Internal il new Internal(s1);//3) 12)id )Uses=i id1, ary 21 Internal i2 new Internal(s2) Defs=iid}N;=N。,P;=P。 22 wriler println(il);//BAD 1) 13)id=meth(ag.…,agn)Uses={arg1,…,argn 23 writer. println (22);//OK 0,P-P VvE Uses(l,),v(l, t, l d, 1)=Prev (ls) 25 public String id( String string)3 !∈1)‖3)‖5)|6)‖12)‖13)→N:=N+(la,Uses(ln) 26 return string: / P i+(ls, v, l d 27} ∈8)‖9)→N=NU{(ln,n1)|n∈Des(la)),P1=p1+(l,,n, 28 该例子主要说明可以跨方法实现对象域访问的依赖关系 14)id,.meth( arg, ... argn )Uses = id,, argI, aIgn I Defs=0 传递,C通过对集合类对象 Hashmap中的表项进行专门建模, 15 )meth( arg,, arg, )Uses=iarg, .. argn Defs=0 跟踪不同常量key值刈应的不同vlue值,实现第5)步。本文 do nothing 1)!∈1)|3)‖5)|6)→N=N+(la,Uses(la)) 实验中对集合类的建模依赖S0OT中的SARK指针分析框 P2=P;+(l,id2,l1)→ 架,它实现了不同key值对应不同的 value,即例中s和s2 lg∈1)‖3)‖5)‖6)‖12|13)→N;=N2+(l4,Is(l)) P,=P,+(Is, id,, L, 指向不同内存位置。 2),4),7).8),9),10),11) similar to l) 3.1C|的不足 对于12)和13),即将方法调用等同于赋值语句,与语句 上述代码屮带下划线的三条语句是本文关注的部分,仅仅 1)类似,只是右操作数不止一个,而是全体参数集合。相应 地,其他语句1)2)4)7)8)9)的转换函数语义作相应扩展。而 使用第2章中形式化描述的CI分析无法判断l是否被污染。 虽然 StringBuffer变量对象$b是通过宇符中对象实例1生成 对于语句14)15),CI分析将忽略这种语句,囚为它不修改任何 b中的字符串信息却由sb. value字符数组表示,逐字节从t 变量,所以不会被任何其他语句依赖。 value数组拷贝过来。根据2.2.3节的依颧关系定义1-5,由 3C方法不足及改进 于拷贝操作的左右操作数都是字符(不是对象),所以无法建 立s.alue与1. value之间的依赖关系。 CI分析使用定义2的依赖关系来解决对象域访问的跨方 CI分析实际关心对象是否被污染,没有考虑具体的简单 法传递问题。即对于22行语句,其数据依赖路径算法5所示类型特别是字符类型的处理。而在We程序中,污染信息主 的1)~6)路径序刎:a)第22行得到.s用于打印(诅是污点要由宇符串表示。因此,文献[10]也特别提到了对丁字符串 携带者 taint carrier,实际污点是ⅱl.s);b)根据依賴定义2和指操作的特殊处理,但是它对字符串的特殊处理是插桩中间代码 针集合的计算结果,第22行使用的变量is依赖于第5行对来完成,通过对所有的Jaa字符中操作进行修收和封装,而且 this.s的定乂;c)恨据依赖定义5,第5行使用的变量s依赖第没有给出具体实现方案。 0行的实参sl;d)实参Ml在18行是调用方法id的返回值,根 恨据3.2节形式化定义建模方法参数的依赖关系,以及各 据依赖关系定义4,它依赖第26行的变量srig;e)变量srig种不同方法调用语句的操作语义,对文献[10描述的依赖关 根据依赖定义5,依赖第18行的m.grt(" fname”)的返回值,而系图进行补充。该定义不仅适用丁宇符串操作方法,也适合其 根据指针分析,m.gf("inme”)的值是在16行根据方法调用他仁意需要专门建模的对象操作方法。 m.put(" tname”,t1)得出,其值为l;f)t根据依赖定义1,依赖 另外对于算法6示例,CI分析也存在问题。由于对象域 于第2行的变量,来自污点输入函数 get Parameter,此时路访问与局部对象变量的依赖关系分别独立建立且互相无关联, 径终止。 导致CⅠ分析出现漏报。12行sink方法使用变量t,t根据依赖 算法5适用CI分析的一个例子 定义1依赖第11行定义的变量1,11行的a.$b根据依赖定义2 I public class Motivating i 只能依赖鎬9行的征s域访问变量,第9行的对象$根据依 2 private static class Internal 3 賴定叉1依赖第8行定义旳对象s,依赖路径结束。 4 public Internal( String s)i 算法6CI分析漏报示例 5 this /12) ring tl= get 6} 2 Class String Bufferloade 7 public String to String()3 8 rel 9} 10 6 StringBufferLoader a 11 protected void doget( Http servleTrequest req 7 String Buffer sb. t: Http servletRespo throws IOException 3 new strin Buffer("hello") 12 String 11 req gel Parameter("Name ):176) 13 String (2=req. getParameter ("IName") 10 sb. append(t1) 14 Print Writer writer resp get Writer () 15 Map m= new HashMap(); 2 write. println( t StringBuffer sb new String Buffer(t1) String s =sb. to String() 这里的主要问题是第10行sb. append(l)没有进入依赖 I=s 路径,囚为根据依赖定义1~5,11行的域汸问变量α.sb与10 I("nN 行的对象变量sb没有建立依赖关系,因此第10行引入的污点 17 IN: t2) 8smig1=( String)id( new Object[n,st("amc")});信息被忽略,从面造成漏报 19 String s2=( String)id( new Object[ I 3.2改进方法的形式化定义 I URLEncoder encode (rm gel("IName: " ))1) 本节对第2章形式化描述的CI分析,增加参数建模的方 3070· 计算机应用研究 第33卷 法调用语句类型16)-19),即其Dcfs集合不为空的情况,如算 在增加新的依赖关系定义6和7后,实际扩展了语句类型 法7所示。对于方法调用语句16)~19),每种方法根据预先3)和5)的前缀集合Prev(l)。定义6、7补充原先的依赖关系, 配置冇不同的Des集合和Deps映射,Defs(l、) CUses(l,)∪将堆变量与局部对象变量的依赖路径联系起来。在为不同方 IeOp(,),Deps:Des(l,)→P(Uses(k) U EloP(l)))。法用语句定义De和Deps以后,语句类型16)~19)的操作 lefOρ指称方法调用谙句的左操作数集合(赋值语句为等式左语义定义需要解决两方面问题:a)它作为游,哪些请句依赖于 值,其他空集);lefs重新定义方法调用语句中可能被修改的它使用的变量;b)它作为目标,依赖于哪些语句定义的变量。 参数集合,而不是默认的左操作数;DPs定义每个D集合中如语句序列 变量在修改过程屮可能依赖的参数集合。 l= getParameter(“ fname”); 算法7增加参数建模方法的操作语义 16)id= id. meth( arg, )Uses=i id sb. append(“hell”); tIn( sb 17)id= meth( arg,, ary )Uses= argI, ary,N,=N,, Pi=P )Uses =I id , arg, -. arg, N,=N, 有第3行使用的变量$依赖于第2行定义的b,第2行定 18)id. meth( arg, Pi=po 义的$依赖第2行使用的$,第2行使用的$依赖于第1行 19)meth( arg,, ". arg. )Uses =i arg N=No P,=p UD+Uses(1s), if(L ,, D)+N,, V(l,, U, Id, 1)pRev(L,) 定义的sb,第1行定义的$依赖第1行定义的t,来自污点 !Ac1)‖3)‖5)|6)‖12)‖13)→N.=N,+(la,Uses(l1),p soURcE P2+(!,,la) 对算法5中 Stringbuffer的构造方法进行建模,定义其ne ∥/÷c8)9)→N=NU(l,v1) U, cDefs(l),p1=p1+(l,n,集合为b,Deps:sb->l,即可直接建立对象s与 4∈16)17)1)19)-Vn;∈Snes(l),i(PA()∩PA(1)≠之间的依赖关系;对 String buffer. ostring方法进行建模,则有 o) Defs集合为{s},Deps:s->{sb},建立s与s之间的依赖关 N,=N,∪{(l,n2)12,∈ Depsls(n1)),P,=P,+(l,,) 1),2),4),7),8),9),10),11),12),13) 系,从而使得算法5中的依赖关系图补充完整。 c16)‖17)‖18)‖19)→ V cADets(l),if(PA(n)∩PA(t1)≠ 对算法6中 String buffer. append方法建模,Defs集合为 ) sb},Deps集合为{sb->{sb,1},此时,PA(a.b)∩P(sb)≠ v,=N,U(Ld, B,)Iv, c Depsls(u,)),P,=p,+(l, v, L,) 3)if(L,, id. id,)t No, V(L,, id. id2, l,, 6)pRev(L,) ⑧,根据依赖定义6,第11行的α.s依赖第10行的s,而第10 a∈16)‖17)‖18)19)→n∈SDes(la),i(P(i…d2)∩行的s在Deps集合中依赖变量t,变量t根据依赖定义1依 PA(n1)≠C) ui( a, B2)lv2 E Depsls(v,)), P:=p 賴第Ⅰ行定义的变量t,来自污点输人方法,依赖路径结東。 5)if(L,, id [id2])EN, V(L,, id,[ id2], la 7)E Prev(l) !}∈16)17)118)‖19)→y1∈SDs(),f(PA(id1i2])n4原型实现 PA(1)≠C) N,=N,Ui(Ld, m,)1v, E Depsls (1,)),P:=P,+(4, id,[id,], Id) 基于2.2节的形式化描述,木文在SO0m0平台上实现原 定义δ语句s类型为3),为类型16)~19),数据依赖型系统(ISTA,指针分析基丁S(OT自带的 SPARK指针分析框 关系s→.id成立当且仅当 架,在 SPARK基础上S0提供了可跟踪虚调用的方法调用 ).id∈Use(s)∧ 图。原型系统实现了两和模块进行实验对比:是直接采用 b)彐a∈Des(t),PA(u)∩PA(u)≠ TAJ的CI分析,对所有局部对象变量进行依赖关系分析,最后 定义7谙句s为类型5),为类型16)~19),数据依赖在依赖图屮根据sink点遍历路径;二是仅对与ink点有依赖 关系s→[id]t成立当且仅当 关系的局部对象变量进行分析,即生成的依赖图中不存在与 a)tid]∈Usc(s)∧ sink点无关的节点。模块二相对于模块一冇效减少了最终依 b)彐u∈Defs(t),PA(u)∩PA()≠ 赖图的规模,实验结果如表1所示 表1TAJ与 CISTA性能对比 WebGoat Boreel CISTA tume time (2 dges(1) edg time(2) 278 079 Phase250889954140330158 4834 21451 1389614683 972 Ve 5l0954 1772 Plase3613038709670 0403 12279265311 17424 223 10023 Ⅴerif61304461506422749 Phase 4 618092 622917 19089 26350 l0876 6 l56 T 8057 19073 20421 Phase 2 81963587756 13896 6428 24713 Phase36130121007356115841 17424 25879 1419 Phase46l80401030950116558 87 19091 7785826000 7 772 19450 原型系统的一些实现细节和策略包括 件的形式提供,目前默认支持 doGet、 dopost、 jspService等常见 a)确定Weh程序的入口方法。入口方法以XML配置文的 Servlet和JSP程序入口,也可以由使用者自行定制。 第10期 郭帆,等:基于依赖的污点分析方法改进研究 3071 b)污点源的指针集合获取。山于souc方法如 actara a)只分析应用程序代码,对所有库方法调用语句t,采用 meter的具体实现无法静态获取,所以算法的污点输入l在统一定义的依赖模型:设t的返回值依赖于所有方法调用参 SPARK指针分析结果中没有具伓的内存位置,即不是对象变数,t的任何参数都不会被其他参数定义。对于发现的漏洞,需 量。 CISTA对 SPARK进行扩展,对预先配置的每个sure方要识别是否虚警,并添加验证方法修补该漏洞;然后再次执行 法所对应的诘句s进行附加处理,将s等同丁new语句进行处该阶段,直到不存在污点传播路径则继续下一阶段。 理,即为母个污点输入合成一个虚拟的初始内存位置,使得后 对丁示例程序,本阶段可发现示例中的路径6→7→8,因 续污点分析正常进行。 为第7条库方法调用语句的返回值a被参数c定义。 c)被分析方法如果 Phantom或者 Native方法,如果该方法 属于需要特殊处理,则按16)~19)类型语句的语义处理,否则 public: String str; TObject( String s)3 this, str= s: i 将该方法调用按12)~15)类型语句的语义处理。 4 TObject( TOBject t), thisstr=tstr d)跨越多个JSP或者 Servlet实例的J2EE全局变量如ses- c= getParameter( test) sion,由于无法获取 vel Allribule和 selAllribule方法的具体代 7 a= b append (e) 码,当前实现仅处理属性名称为常量的情况,通过维扩全局属 8ou. println(a);/阶段1 性名列表来跟踪对应的内存位置。对于属性名为变量的情况 9 d append(c) 0out. println(d);//阶段2 CISTA未作处理。 11 f= new TObject(c) e)反射方法处理。当前反射方法的识别和建模依赖 12out. println(f.sr);//阶段4 13 k= new TObject(f) SOOT提供的反射框架。SOOT提供了 dynamic-cas选项支持 14 f, str= c 反射方法的识别,在方法调用图中集成了跟踪反射调用的实际 15out. println(k.str);/阶段3 Java方法。 b)对于类型16)~19)语句,由开发人员在配置屮专门建 f) Source、ink和 sanitizer三类方法都以ⅹML配置文件的模,不需要深人库方法代码分析,其他库方法与应用程序代码 形式提供,系统默认提供常见的 source和sink方汏, sanitizer相同处理。如果对冇关方法进行了精确建楨,即可精准发现有 需要由使用者定制。实验中使用的 source和sink卞要是针对关安全漏洞和依赖路径,在人工确认和修补并验证后继续下 Wb注人攻击如 SQLIA和XS攻击而设置。它们在分析中作阶段。 为 Native方法处理,不需要深入其代码进行分析 对于示例程序,如果对第9行的 append方法建模,指明对 4.1优化依赖路径遍历 象α会被参数c定义,则可建立依赖路径6-9→10。如果对示 在生成的依赖图中,人口节点(即没有入边的节点)包括 例中 TObject类也釆用3.2节方法建模,则无法发现依赖路径 入口、 source和 sanitizer方法,它们是每条依赖路径的最后一个123-6和15→14→6,因为方法建模忽略了方法的副 节点,出口节点即为smk方法。在实验中,Weo程序的作用。 sink节点多达618个。由于本文的分析包含完整的Java基础 c)对阶段2进一步细化,对参数为字符串对象或者字符数 类库,图中的边和节点数以万计,使得依赖路径数量巨大。由组的类型16)~19)语句,采用专门建模,其他库方法正常处 丁实验在4CB物理内存下最大只能设置为130M虚拟机理。因为字符串操作类方法与Wc程序的安全漏涧关系非常 内存,巨大的依赖图使得虚拟机内存消耗殆尽,导致大量时间奈密,而且程序中大量使用字符串操作,仅对它们进行专门建 耗费在内存管理部分,从而极大地影响了分析性能。 模就可以减少依赖图规模,有效减少分析时间。 文献[16]采用LCP( last call point)方法进行简化,即不遍 对于示例程序,第12条语句的方法调用没有采用建模,使 历仝部依赖路径,只用路径中的三个节烹表示,从而减少遍历 得第4条语句的构造方法可以展开分析,因此本阶段新发现依 时间,但是分析结果不精确。 赖路径1544→14-6。 本文釆用迭代求精方法来遍历所有依赖路径,将分析 d)正常处理调用图中的仝部库方法代码。由于前三阶段 切分为多个阶,每个阶段都在上一阶段完成漏洞修正以后才已经做了许多漏润修补工作,剩余漏洞通常不会很多,使得木 进行,漏洞修正通过人T在依赖路径中增加验诎方法来实现 阶段生成的依赖图规模有限,可在有效时间内完成。 每一个潜在漏洞被修正使得有关依赖路径终止,下一阶段分析 对于示例程序,该阶段对第11条语句不采用建模,使得笫 不再需要处理有关路径。即分析不需要一次性得到所有可能3条淠句的构造方法可展开分析,发现新依赖路径123-6 路径,而是找到一部分路径就先修正一部分,再次分析的结果 CISTA的路径遍历方法如下:在每阶段生成依赖图后,采 就不会再包含这部分路径。该方法基于这样一种假设,即普通用 Floyd-Warshall算法计算每条in话句的日标变量到 wb程序在经过测试后,其安全漏润并不会有很多,如果在分达其他节点的可达性;然后采用文献16是出的LCP方法,只 析的早期阶段发现某漏洞并修正后,后续分析中很多由该漏洞 算每条路径中的几个关键节点,本文实验对每条路径使用四 引发的依赖路径就不会出现在依赖图中,从而减少后续分析的个节点。需要说明的是,每条路径的节点数可以由开发人员自 作量。例如,如果在某条依赖路径上存在验证方对边行设置,因为所有节点间的可达性都已经计算得到,在人工确 c的源变量进行了验证,那么c后面的依赖子树就可以在后续定漏涧的具体位置时,开发人员可以根据需要增加节点数以便 分析屮被删除,从而减少依赖图的规模。 于精确定位漏洞 CISTA支持将系统分为四个阶段进行分析,每个阶段都需42不足之处 要完成生成依赖图、遍厉依赖路径、漏洞修复、验证四个过程。 1)依赖图不精确当前仅进行CⅠ分析,并采用SOOT自 本节以下面的程序片断来说明四阶段分析 带的 SPARK指针分析框架。虽然污点分析是流敏感的,但是 3072· 计算机应用研究 第33卷 指针结果是流不敏感的,造成生成的依赖图规模巨大;而文献 从 Bodcglt的实验数据可看出,对于小型Web程序采用达 [25]的实验表明不精确的指针分析对依赖图的规模影响巨代求精方法,毎个阶段都可以较快得到分析结果。如果不采用 大,未来需要集成精确的上下文敏感和流敏感的指针分析,并迭代方法,直接包含全部库方法进行分析,耗时也较长。模块 相应修改 Jimple_S的操作语义 即使经过前三阶段的分析和验证,在第4阶段直接包含所有 2)传播路径不精确 CISTA日前仅对每条路径记录四个厍方法进行分析,仍然需婁耗吋77725,而且需婁对生成的 节烹点,虽然可以根据用户需要扩展,但是扩展每条路径的节点19450条路径花费几个小时进行人工确认和修补 数会造成分析时间大大增加。如何快速提取精确的路径是木5.2精度分析 来的工作方向。 由于应用TAJ无法基于 SPARK指针分析框架完成Wclh 5实验分析 Goat网站分析,实验针对 bodgelt网站将1AJ与 CIstA进行分 析结果的精确度对比, CISTA采用多阶段分析法,TAJ不采用 5.1性能分析 多阶段分析法,分析结果如表2所示。 表2精确度对比分析 应用CSTA对两个2EEWc漏洞演示网站 Bovell2和 WebLoad3进行实验,实验结果如表1所示。两者者基于JP 方法漏洞数量时间/s 1840 开发, Bodvel程序规模3000行左右, WebGoal程序规模 CISTA 95 359 17000行左右。 分析开始吋根据对象域访冋和数组元素访问的依赖关系 表2给出的漏洞数量是在没有设置任何验证方法的条件 定义(定义236、7),建立相应语句之间的依赖边总数(第2下生成的。以(orce,sink)对为基本单位,只要从sure到 列),即先建立堆变量依撷图。分析结東时生成依赖图的总边sink至少存在条依赖路径,则找到个漏洞。TAJ的分析时 数和节点数分别由第3和4列表示。第5列的时间是指生成间1840s相比表1中时间较少,是因为原始的TN没有应用 依赖图的时间,第6列是从依赖图中获取依赖路径的时间,单3.2节的改进方法,所以其精确度不高。基于3.2节定义的改 位为5。第7列是依赖路径数量。 Phasc1-4对应四个阶段。 进, CISTA发现了95个漏洞,而TAJ仅发现了55个漏洞。算 CISTA表示模块2,TAJ表示模块1。实验过程如果不采用4.1 法8给出一个实际位于 Bodgelt网站 login.jsp文件中的漏洞, 节方法遍历依赖路径,那么会由于依赖图路径数过多而无法在 TAJ没有报告该漏泂,示例中标下划线部分即为依赖路径的有 有限时间内计算完毕。Veri表示漏洞修补后的验证分析。 关语句。 比较第2列和3列,可以发现堆对象的依赖边占依赖图的 算法8个实际的漏洞示例 (a)有漏洞的Java代码 大部分,特别是对于模块二。因为模块二仅根据用户需要跟踪 boolean loggedIn=fal 的sink点来分析局部对象变量,而模块一是对所有的局部对 String username = String)request. get Parameter("username 象变量分析,表明后续的依颧图分析实际主要分析堆变量。从 String password = String) request getParameter("pass word")i 第4、5列叮以看出,构建依赖图的时间并不多,主要时间花费 f (request. getMethod () equals("POSt")&& username 在提取依赖路径(或污点传播路径)上。 Statement stmt conn ereateStatement() 可以看出,即使釆用迭代求精方汰使用模块二进行分析, Resultset rs= nu 第2和3阶段的总路径数达到21451和6531条,而且每条 rs= stmt. execute Query("SELECT s FROM Users WhERE(name 路径仅包含四个节点,除了 source和sink以外,分别包含 t username source和sink可达的库边界节点。实际上一对( Source if(rs next())1 可能包含数千条路径在实验中对阶段2和3的漏洞验证过 (b)对应的 Jimple代码 程,分别花费2和4h增加验证方法和排除虚警,使得验证后 tempMYM6= request. getParameter("username") 的分析不再找到依赖路径( Verify行的路径数为0)。 WebGoat username=temp S 6: 实验的阶段2耗时4834s,而阶段3耗时122792s,时间大量 temp S 12 new java. lang String Buffer 消耗在枚举依赖路径过程。在人工排除漏泂和虚警后,依赖图 temp$12.〈init)() temp 12 append( "SElECt s FROM Users WhERE (name 中的节点数分别从30158和60403下降至17722和22749, 而分析吋间相应下降至124s和233s。这些结果表明在安全 ap S 12. append( username); temp S 12. append ("\ and password =\" 漏洞较少的Weh程序中,分析可以在较短时间内完成。在阶 lemp S 12. append( password) 段3宄成验证后,阶段4中没有找到新的路径,这正好说明阶 temp S 12. append ("1") 段3的必要性,分析不需要讲入与字符串有关的操作方法也可 temp s 14= stmt. execute Query( temp 13); 得到精确的分析结果。 rs =temp s 14 模块一(TAJ)同样按照四个阶段分析,但是仅分别计算其 TAJ未能发现该漏洞的原因是缺乏对 append和 tostring 依赖图,没有计算最终路径数和相应时间,因为路径遍历时间方法的建模,使得snk变量temp$13无法建立与变量uer 过长(超出72h)。对图的规模进行比较即可看出,模块一在ime的依赖关系,从而造成漏报。 WebGoat实验的第2和3阶段的节点数分别为87756和 115841,远远超出模块二中对应阶段的节点数,因此其分析时 6结束语 同也远远超出。 本文对面向JEE程序的基于数据依赖的静态污点分析进 第10期 郭帆,等:基于依赖的污点分析方法改进研究 3073 行形式化定义,以中间代码语言 Jimple的子集 Jimple_S为抽象 arski-Knaster theorem 目标语言形式定义各类Java变量在 Jimpls_s程序中产生的直161 Tripp u, Pistoia m,hnkS.1AJ: effective taint analysis of Web ap- 接依赖关系,给出描述程序数据依赖图的抽象状态空问并证明 plications[ C]// Proe of ACM SIGPLAN conference on Programmin 其为完备格,形式定义 Jimmpls_s语句传播依赖关系的操作语义。 Language Design and Implementation. New York: ACM Press, 2009 本文针对现有方法的不足,提出并形式定义使用专用方法建模[17] Sridharan M, Fink sj, Bodik R. Thin slicing[ C]/ Proe of ACM 来增强方法调用参数与堆变量之间的依賴关系,完善原有方法 SIGPLA Conference on Programming Language Design and Imple 应用迭代求精的分析方法解决目标依賴图中存在的路径爆炸问 mentation. New York. ACM Press.2007.112-122 题,对开源网站平台的实验分析表明迭代方法的有效性 [18 Wasserman G, Su Zhendong. Static detection of eross-site scripting 参考文献 cabilities[ C]//Proc of International Co onerence on soltware E [1 Ray D, Ligatti J. Defining code-injection attacks[ C]//Proc of ACM neering. New York: ACM Press, 2008: 171-180 ymposium on Principles of Programming Languages. New York: ACM [19 Christian K, Anders M. Static analysis for Java servlets and JsP [C//Proe of Analy [2 Livshits V B, Lam M S. Finding security vulnerabilities in Java appli 2006:336-352 cations with static analysis [C]// Proc of USENIX Security Sympo [20] Carl G, Su Zhendong, Premkumar D. Static checking of dynamically generated queries in database applications[ C]//Proc of International sium. Berkeley: USENIX Association, 2005 18-33 Conference on Software Engineering. S.I.: IEEE Press, 2004 [3 Newsome Song D. Dynamic taint analysis for automatic detection 45-654 signature generation of exploits on commodity software [21 Wasserman G, Su Zhendong. Sound and precise analysis of Web al ACM Symposium on Network and Distributed System plications for injection vulnerabilities[ C]//Proc of ACM SIGPLAN Security. San Diego: Internet Society, 2005 Conference an Programming Language Design and Implermeritalit [4 Schwartz E. J, Avgerinos T, Brumley D. All you ever wanted to know New York: ACM Press. 2007:32-41 about dynamic taint analysis and forward symbolic execution but [22]Son 5, McKinley K S, Shmatikov V. Diglossia: detecting code injec- might have been afraid to ask )[C]//Proc of IEEE Symposium on Se tion attacks with precision and efficieney[c //Proe of ACM Con curity and Privacy. [SI.]: IEEE Press, 2010 317-331 rence Computer and Communicationg Security. New York: ACM [5 Jovanovic N, Kruegel C, Kirda E. Pixy: a static analysis tool for de- Press,2013:ll8l-1192 tecting Web application vulnerabilities[C]//Proc of IEEE Symposium [ 23] Su Zhendong, Wassermann G. The essence of command injection at- on Security and Privacy. [S. 1.]: IEEE Press, 2006: 263-268 acks in Web applications[ C]// Proc of ACM Symposium on Princi 1 6 Jovanovic N, Kruegel C, Kirda E. Static analysis for detecting taint- ples of Programming Languages. New York: ACM Press, 2006: 372- style vulnerabilities in Web applications[ JI. Joumal of Computer 382. Security,2010,18(5):861-907 L24」王溢,李舟军,郭溽.防御代码注入式攻击的字面值污染方法 「7梅宏,王啸吟.张路.字符串分析硏究进展「J.软件学报,2013, J].计算机研究与发展,2012,49(11):2414-2423 24(1):37-49 [ 25] Bandhakavi S, Bisht P, Madhusudan P. CANDID: preventing SQL [8 Martin M, Livshits M, Lam M S Finding application errors and secu ction alla ks using dynamic candidate evaluations C]//Proe of rity flaws using PQL: a program query language[C]//Proc of ACM ACM Conference on Computer and Communications Security. New SIGPLAN International Conference on Object-Oriented Programming York: ACM Press. 2007: 12-24 Systems, Languages, and Applications. New York: ACM Press, 2005 26] Bisht P, Venkatakrishnan V N. XSS-GUARD: precise dynamic pre- 365-383 vention of cross-site scripting attacks[ C//Proc of International Con [9]黄强,曾庆凯.基于信息流策略的污点传播分析及动态验证[J ference on Detection of Intrusions and Malware, and Vulnerability As 软件学报,2011,22(9):2036-2048 sessment..S1.]: Spring Press, 2008: 23-43 「10]孙浩,李会朋,曾庆凯.基于信息流的整数漏泂插装和验证「J [27] Horwitz S, Reps 'T', Binkley D. Interprocedural slicing using depe 软件学裉,2013,24(12):2767-278 dence graphs[ C]// Proe of ACM SIGPLAN Conference on Program- I 11 Xie Yichen, Aiken A. Static detection of security vulnerabilities in ming Language Design and Implementation. New York ACM Press 1988:26-60 stripling languages[ C J //Pme of USENIX Security Symposilln [28] Gopan D, Reps T. Guided static analysis[ C]//Proc of International Berkeley: LSENIX Association 2006:179)-122 Static Analysis Symposium. [S Springer,2007:349-365 12] Son S, Shmatikov V. SaferPHP: finding semantic vulnerabilities in [29] OWASP. OWASP Lapse projet[ EB/OL].[ 2015-04-15].hI PHP applications [C] //Proc of ACM SIGPLAN Workshop on Pro tps//www.owasporg/index.php/owasp_lapse_projeEt and Analysis for Security. New York: ACM [30] Lam P, Bodden E. Soot: a framework for analyzing and transforming Press.2011:1-1 JavaandAndroidapplicationsEb/oL.[2015-11-02.http:/ [13 Dahse Holz T. Simulation of built-in PHP Features for precise sta- www.sablemcgillca/soot tic code analysisL C J//Proc of ACM Network and Distributed System 131| Warshall F. Floyd-Warshall algorithmL EB/OL]. L2015-10-27Jht ecurity Symposium. San Diego: Internet Society, 2014: 1-15 tp: //en. wikipedia. org/ wiki/ Floyd-Warshall_algorithm 14 Huany Yanwen, Yu Fang, Hang C, et ul. Securing Web applicalion 32GoogleInc.TheBodgeltstoreEb/oLj.2015-03-15.http:/ code by static analysis and runtime protection[ C]//Proc of the 13th ode. google. com/p/bodgeit Internalicnal Conference on the World Wide Web. New York: ACM [ 33]OWASP. Category: OWASP WebGoat project[ EB/OL]. [2015-08 21.https://www.owasp.org/index.php/category:Owaspweb- [15 Tarskit K. Tarski-Knaster theorem[ EB/OL].2015-03-15.ht oat project

...展开详情
试读 9P 论文研究-基于依赖的污点分析方法改进研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

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

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于依赖的污点分析方法改进研究.pdf 39积分/C币 立即下载
    1/9
    论文研究-基于依赖的污点分析方法改进研究.pdf第1页
    论文研究-基于依赖的污点分析方法改进研究.pdf第2页
    论文研究-基于依赖的污点分析方法改进研究.pdf第3页

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

    39积分/C币 立即下载 >