C程序控制流程模型的提取技术与实现

控制流图描述了函数执行时可能采取的执行路径。绝大多数静态分析工具都在抽象语法树之上生成控制流图并据此对程序的运行行为进行分析。在模型检测过程中,提取正确的控制流图是构建系统模型的关键。在分析C程序的抽象语法树和控制结构的基础上,设计并实现了程序控制流图提取的算法,并分析了算法的正确性。基于提取的控制流程,可对C程序的某些性质进行模型检验。     

基于路径覆盖准则的AOP路径生成方法研究

在检验面向方面程序质量时,常常会依据路径覆盖准则对其进行测试,所以生成符合路径覆盖准则的AOP路径是很重要的。生成AOP路径,对AOP的控制流信息进行分析、表示,构造其单个模块、基本方面等的语句控制流图,确定类与方面之间交互的表示方法,构造出完整AOP语句控制流图;遍历完整AOP语句控制流图,得到从源节点到终节点的所有路径,这些路径中的可执行路径即是满足路径覆盖准则的测试路径。     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

基于Define-Use分析的冗余通信消除算法

针对并行代码自动生成过程中产生的大量冗余通信代码,提出基于Define-Use分析的冗余通信消除算法。将中间代码的每一个过程划分为不同的块,同时收集各块中对数组变量的定义和引用信息。以块为节点,按控制流关系构造控制流图。以控制流图为基础,根据块间各数组变量的Define-Use关系,确定需要通信的位置,从而消除冗余通信代码,达到优化通信的目的。测试结果表明,该算法可有效提高并行程序的执行效率。     

Java自动化基本路径测试研究

针对Java单元测试自动化程度和测试效率较低的问题,对基于Java程序的基本路径测试方法进行研究,提出了基于Java代码的基本路径生成方法和程序插桩方法,给出了插桩节点和控制流图节点的定义。首先,通过对Java源代码进行分析,构建程序的控制流图,进而对控制流图进行遍历生成基本路径集合;然后,对被测程序进行插桩,以获取程序的执行路径,插桩过程中保持节点和基本路径中的节点一致,使得插桩后的被测程序执行时得到的路径能够和基本路径集合进行自动化比对;最后,通过以测试数据为输入执行被测程序,对执行路径和基本路径进行比较,判断测试数据集对基本路径的覆盖度。通过实验,验证了所提出方法的有效性。     

基于自动路径驱动的动态控制流恢复算法

动态控制流恢复方法存在路径覆盖不全的问题。为解决该问题,提出一种基于自动路径驱动的控制流恢复算法。在可控的模拟调试环境中动态执行并分析二进制程序,通过修改CPU程序计数器的值,使驱动程序执行在当前输入条件下无法访问的程序路径,从而构建控制流图。基于该算法,设计实现自动路径驱动控制流恢复系统。测试结果表明,该算法能够较全面地发掘程序执行路径,与传统动态执行算法和交互式反汇编器相比,能有效提高恢复控制流图的覆盖率。     

基于最优子序列双射的骨架树匹配

基于图描述的骨架图匹配大多考虑骨架图的拓扑结构,使得匹配精度受到影响。先通过骨架构造以骨架中心为根节点的骨架树,使用骨架中心到骨架端点测地路径等信息来描述骨架树的叶子节点,利用改进的最优子序列双射时序匹配算法来确定两幅骨架树叶子节点的匹配关系,该算法不考虑骨架树的拓扑结构,只匹配骨架树的叶子节点。通过匹配实验结果和检索实验结果,表明该方法有效地提高了匹配精度。     

流敏感按需指针别名分析算法

为了提高交互环境下指针别名查询的响应效率,近期研究提出通过只分析与目标相关指针的按需分析策略来降低浪费在与目标无关的指针分析的额外开销。典型的代表是基于上下文无关文法的按需别名分析算法。但是,该算法的精度只局限于控制流不敏感。控制流不敏感的别名关系将约束上层分析的精度。针对该不足,提出了具有流敏感精度的按需别名分析算法。首先采用不完全静态单赋值语句形式来区分指针变量赋值实例,然后通过层次线性化编码方法来表达控制流图中的流敏感信息以构建赋值流图,最后将别名关系查询问题转换为在赋值流图上搜索目标结点间在控制流可达条件下赋值路径的可达性问题,进而实现流敏感的按需别名分析。实验表明,与流不敏感的按需别名分析相比,该方法可以在保证查询效率的前提下,有效提高按需别名分析的精度。     

一种工作流的控制流距离度量方法

为准确计算工作流中的控制流距离,提出一种工作流的控制流距离度量方法.介绍从工作流中分离控制节点生成控制流图的过程.在控制节点间距离基础上,建立通过控制流图进行工作流控制流距离度量的模型,并从理论上证明距离度量模型满足自反、对称及三角不等式性质.案例分析结果表明,该方法能更真实、准确地反映工作流间的距离.     

针对能耗热点的SPM静态分配管理策略

综合考虑程序的指令块、数据块、全局变量对程序执行能耗的影响,使用带权重扩展控制流图（WECFG）将应用程序划分成各类逻辑节点,通过SPM平均访问能耗值计算出逻辑节点平均能耗,以及各逻辑节点的能耗密度。以能耗热点为依据构造SPM分配的整数线性规划算法（ILP）,转化成以能耗密度为优先权的0-1背包算法。仿真结果表明,使用该分配策略的SPM空间分配,比不使用SPM时的能耗量平均减少34.8%左右。     

一种面向二进制的控制流图混合恢复方法

控制流图恢复是进行二进制文件安全性分析的基础,静态恢复分析速度快,但其精确度欠缺;动态恢复方法的优点是精确度高,但分析效率较低。将两者优点结合,提出了面向二进制程序的混合分析恢复方法,在对二进制文件进行静态分析生成控制流图的基础上,结合局部符号执行技术和反向切片技术对间接分支跳转的目的地址进行求解,之后再分析边和节点的可达性,合并不可达的边和节点。经实验验证,混合方法的分析效率与静态方法相近,远高于纯动态分析方法,其精确度较静态方法有较大提高。     

树形探测法及其在矿井排水智能流向计算中的应用

提出了确定复杂管路网络中流体流向的计算方法--树形探测法,通过将管路网络转化为树形拓扑结构,借助基于仿生算法的树形递归原理,在已知节点驱动类型的基础上,确定流体在整个系统各环节的流向。借助计算机语言C#,利用泛型参数技术、接口技术和基于委托技术的Observer设计模式实现了“树形探测法”通用组件接口。该算法被应用于神华神东锦界煤矿复杂排水系统的计算机仿真平台中,将闸阀、水泵和接头作为节点,管道作为边,利用树形探测法确定水流流向,应用效果较好。     

基于基本块标识方法的控制流图生成器设计

设计一个实用的程序控制流分析工具需要解决非结构程序中goto等语句的控制流图构造问题。C语言程序控制流图生成器CfgGen的设计采用基于基本块标识的控制流图构造方法解决该问题。CfgGen程序基于规则,通过语法制导翻译标识基本块、构造控制流图,易移植和维护。CfgGen构造的控制流图标识了基本块,可以很方便地用于程序分析和优化。     

Approximation Algorithms for a Capacitated Network Design Problem

We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to support the flow at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio (ρ_ST + 2) where ρ_ST is the performance ratio of any approximation algorithm for the minimum Steiner tree problem. When all sources have unit demand, the ratio improves to ρ_ST + 1) and, in particular, to 2 when all nodes in the graph are sources.     

继电控制线路的网络拓扑图的生成与再次抽取

继电控制线路原理图可以抽象为网络拓朴图。该文介绍了一种由继电控制线路原理图的几何图形生成网络拓扑图的算法,并且根据对继电控制线路分析的需要,去除了原拓扑图中的无效边和无效节点,对原拓扑图进行了再次抽取,使得整个拓扑图的结构大为简化,这样就可以大大提高时拓扑图进行分析和运算的速度,该文的结果在继电控制线路的计算机辅助设计与分析中有重要意义。     

嵌入式控制系统程序模式的自动分析方法

嵌入式控制系统通常都有模式,比如启动模式、正常工作模式以及紧急模式等。程序模式是由其输入变量值范围组合构成的输入变量约束表达式表示的。基于源程序,获取其模式,不仅能够验证实现的模式与设计是否一致,还能够更加精确地计算程序的WCET。在对源程序进行分析的基础上,提出了一种自动获取程序模式的新方法。该方法基于C语言源程序,针对程序控制流程图,通过调整循环中节点流向以及去除与输入变量无关的节点,获得输入变量相关控制流程图ICFG,通过对ICFG每条路径建立线性规划问题并求解,获得每一个潜在的程序模式及其输入变量约束表达式。对基准程序的实验结果,表明了该方法的可行性和有效性。     

软件定义网络流的安全要素知识图谱研究

流表是软件定义网络控制平面与数据平面交互的核心组件,也是实现安全策略全局协同及动态映射的关键。然而,构建具备相关安全策略的流表却需应对流知识要素过于分散、不断扩充、难以通过独立应用或预设规则满足等诸多难点。针对这一现状问题,本文通过采取在软件定义网络控制、数据和应用等三大平面之外新建知识平面的方式,构建流表及其相关安全知识要素聚集的流知识图谱,并基于此选择或生成流表规则。在流规则选择方面,构建同源-目的地址单条/合成流规则合并的流规则搜索树并关联流知识图谱,达到对已有流规则快速选择并决策的目的;在流规则学习生成方面,以流规则搜索树图融合的方式分裂生成流规则安全决策图,以此根据流标记生成或选择流规则。在评估部分,本文通过与应用平面交互、流规则选择、流规则学习等三个角度观察流知识图谱的实际应用方向及可能性,并通过实验衡量了基于流知识图谱的关键算法性能。以流知识平面的图谱等为基础设施,可近一步深入具体场景,通过流安全标记与应用相结合的方式,促进流规则演进等实践开展。     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

流向图回溯法及传输网络From-To解算方法和技术研究

针对传输网络中流体“从哪里来,到哪里去”的确定问题,基于图回溯法,提出了一种基于流向图的传输网络From-To解算方法.根据传输网络中的驱动点、管道、闸阀和出口各属性状态,将整个网络转化为初始流向图拓扑结构,根据图回溯原理,逐步累积计算管道中流体的来源和去向,直到全部管道回溯结束,得出最终流向图.在此基础上,研发了基于Observer设计模式的“From-To解算”通用组件接口,并被应用于某大型煤矿的复杂排水管网的计算机仿真平台中,应用效果较好.     

Graph construction with the maximum number of trees by continuous edge addition

A simple computational algorithm is presented to construct a graph with the maximum number of trees by adding edges one by one. The number of trees of a graph would become an index to estimate the overall reliability of probabilistic communication networks with the same link probabilities. Our procedure, Max-trees, selects one edge that gives the maximum number of trees among edges not included in the original graph. This process is continuously repeated at each step of adding an edge, when we get the sequence of new edges to be added. As examples of the execution results, the edge sequence and the maximum number of trees are shown for two types of starting graph, which are a tree of series edges and a star-shaped tree for nodes n = 7 and 8. To see how many trees these graphs have, the minimum numbers of trees for graphs with the same number of nodes and edges are similarly calculated by the minimum-version algorithm Min-trees. An edge sequence of Max-trees makes long cycles, and that of Min-trees makes cycles of three for as long as possible. The ratio of the maximum number of trees to the minimum number of trees is about 1 to 6 for these examples. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006