CAJ | 학술논문

为了提高交互环境下指针别名查询的响应效率，近期研究提出通过只分析与目标相关指针的按需分析策略来降低浪费在与目标无关的指针分析的额外开销。典型的代表是基于上下文无关文法的按需别名分析算法。但是，该算法的精度只局限于控制流不敏感。控制流不敏感的别名关系将约束上层分析的精度。针对该不足，提出了具有流敏感精度的按需别名分析算法。首先采用不完全静态单赋值语句形式来区分指针变量赋值实例，然后通过层次线性化编码方法来表达控制流图中的流敏感信息以构建赋值流图，最后将别名关系查询问题转换为在赋值流图上搜索目标结点间在控制流可达条件下赋值路径的可达性问题，进而实现流敏感的按需别名分析。实验表明，与流不敏感的按需别名分析相比，该方法可以在保证查询效率的前提下，有效提高按需别名分析的精度。
위료제고교호배경하지침별명사순적향응효솔，근기연구제출통과지분석여목표상관지침적안수분석책략래강저낭비재여목표무관적지침분석적액외개소。전형적대표시기우상하문무관문법적안수별명분석산법。단시，해산법적정도지국한우공제류불민감。공제류불민감적별명관계장약속상층분석적정도。침대해불족，제출료구유류민감정도적안수별명분석산법。수선채용불완전정태단부치어구형식래구분지침변량부치실례，연후통과층차선성화편마방법래표체공제류도중적류민감신식이구건부치류도，최후장별명관계사순문제전환위재부치류도상수색목표결점간재공제류가체조건하부치로경적가체성문제，진이실현류민감적안수별명분석。실험표명，여류불민감적안수별명분석상비，해방법가이재보증사순효솔적전제하，유효제고안수별명분석적정도。
In order to improve the response efficiency of pointer alias queries in the interactive environment ,researches are interested in the demand driven strategy to reduce the cost for analyzing the unrelated pointer variables with respect to the objectives .The demand driven alias analysis based on the context free grammar has been proposed .However ,its precision is only limited to the flow‐insensitivity .The flow‐insensitivity pointer alias restricts the precision of overlying analysis ,so the bug detection results in more false alarms than the one with flow‐sensitive alias analysis .In this paper ,we propose a demand driven pointer alias analysis based on the graph reachability and the context free grammar to provide the flow sensitive precision ,which has tolerable additional overhead comparing with the flow‐insensitive alias analysis . First the updates of pointer variables are discriminated by the partial single static assignment to filter out the unrelated pointer variables as early as possible .Then the sequence of control flow along these assignments is expressed in the form of level linearization code ,which is used to construct the assignment flow graph .Finally ,the query of alias in demand driven is formalized as the search of reachability of target nodes in the assignment flow graph to achieve the precision of flow sensitivity .The experiments demonstrate that this presented method can improve the flow sensitivity the precision of alias analysis in demand driven with overhead tolerable .