A Complexity Measure

This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph-theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual Fortran programs are then presented to illustrate the correlation between intuitive complexity and the graph-theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program.     

Using Vapnik–Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments

We examine the complexity of testing different program constructs. We do this by defining a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik–Chervonenkis dimension, and applying it to classes of programs, where all programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine that a program is approximately correct, so by studying it for a class of programs we gain insight into the difficulty of testing the program construct represented by the class. We investigate the VCP-dimension of straight line code, if–then–else statements, and for loops. We also compare the VCP-dimension of nested and sequential if–then–else statements as well as that of two types of for loops with embedded if–then–else statements. Finally, we perform an empirical study to estimate the expected complexity of straight line code.     

Cyclomatic complexity density and software maintenance productivity

A study of the relationship between the cyclomatic complexity metric (T. McCabe, 1976) and software maintenance productivity, given that a metric that measures complexity should prove to be a useful predictor of maintenance costs, is reported. The cyclomatic complexity metric is a measure of the maximum number of linearly independent circuits in a program control graph. The current research validates previously raised concerns about the metric on a new data set. However, a simple transformation of the metric is investigated whereby the cyclomatic complexity is divided by the size of the system in source statements. thereby determining a complexity density ratio. This complexity density ratio is demonstrated to be a useful predictor of software maintenance productivity on a small pilot sample of maintenance projects     

消息传递并行程序的弱变异测试及其转化

并行程序执行的不确定性,增加了测试的复杂性和难度.研究消息传递并行程序的变异测试,提出其弱变异测试转化方法,以提高该程序变异测试的效率.首先,根据消息传递并行程序包含语句的类型和语句变异之后导致的变化构建相应的变异条件语句;然后,将构建好的所有变异条件语句插入到原程序中,形成新的被测程序,从而将原程序的弱变异测试问题转化为新程序的分支覆盖问题.这样做的好处是,能够利用已有的分支覆盖方法解决变异测试问题.将该方法应用于8个典型的消息传递并行程序测试中,实验结果表明,该方法不但是可行的,也是必要的.     

基于隔离逻辑的并行程序可靠性验证方法

并行程序验证的复杂性在于执行流程的不确定性以及由此导致的执行规模变大,使得验证的内容和目标之间的关系不明确。为解决该问题,提出一种基于隔离逻辑的并行程序可靠性验证方法。通过变量的执行关系图,描述变量相关的语句及执行关系,将所需验证的程序性质逻辑式转换为变量并行语句序列的逻辑组合式,使得性质表达式与并发程序的语句相关联。根据逻辑组合式确定语句执行序列和前后件逻辑表达式,基于并发隔离逻辑的公理系统对语句执行序列进行验证,并根据验证结果对并发程序进行修改和完善。通过对银行柜台业务办理的功能模块验证结果表明该方法是有效的。     

Generation of correctness conditions for imperative programs

Verification of imperative programs in the sense of Floyd-Hoare is an approach to proving correctness of programs annotated by preconditions, postconditions, and loop invariants. It is based on generation of correctness conditions. In the structured deterministic case, the problem of generation of correctness conditions seems trivial, since it is solved by a syntax-driven algorithm, the complexity of which linearly depends on the number of control constructs. Vice versa, in the unstructured nondeterministic case, it seems a priori clear that the complexity of generation of the correctness conditions exponentially depends on the number of statements in the program. In the paper, an efficient and complete algorithm for the generation of the correctness conditions is presented and justified. It can be used both in the structured deterministic and unstructured nondeterministic cases. The algorithm complexity linearly depends on the number of control constructs and/or program statements.     

A characterization of span program size and improved lower bounds for monotone span programs

We give a characterization of span program size by a combinatorial-algebraic measure. The measure we consider is a generalization of a measure on covers which has been used to prove lower bounds on formula size and has also been studied with respect to communication complexity.?In the monotone case our new methods yield lower bounds for the monotone span program complexity of explicit Boolean functions in n variables over arbitrary fields, improving the previous lower bounds on monotone span program size. Our characterization of span program size implies that any matrix with superpolynomial separation between its rank and cover number can be used to obtain superpolynomial lower bounds on monotone span program size. We also identify a property of bipartite graphs that is suficient for constructing Boolean functions with large monotone span program complexity. Received: September 30, 2000.     

程序复杂性度量的一种新方法

通过分析传统的程序复杂性度量方法的不足之处，首先提出了一种基于程序分解机制的路径复杂性度量方法，然后给出了计算路径复杂度的算法，最后给出了实例。新的度量方法指出了一个程序需要的完全测试路径数目。     

路径复杂性度量研究

软件复杂性度量是对程序静态特性和动态行为的理解难易程度的描述。本文通过分析传统的程序复杂性度量方法的不足之处，提出了一种新的路径复杂性度量方法及计算路径复杂度的算法，并给出了实例。新的度量方法比传统的度量方法更精确和容易实现。     

Program complexity using Hierarchical Abstract Computers

A model of program complexity is introduced which combines structural control flow measures with data flow measures. This complexity measure is based upon the prime program decomposition of a program written for a Hierarchical Abstract Computer. It is shown that this measure is consistent with the ideas of information hiding and data abstraction. Because this measure is sensitive to the linear form of a program, it can be used to measure different concrete representations of the same algorithm, as in a structured and an unstructured version of the same program. Application of the measure as a model of system complexity is given for “upstream” processes (e.g. specification and design phases) where there is no source program to measure by other techniques.     

融合语句复杂度的软件错误定位轻量级方法

在程序调试过程中,基于程序谱的软件错误定位(SBFL)技术能提供有效的帮助。为改善SBFL的性能,提出一种组合程序谱、代码行静态属性的软件错误定位排序学习方法,由线性排序支持向量机学习最优错误定位模型。代码行静态属性包括局部变量、类属性、逻辑运算符和方法调用等程序实体的个数。在使用C、C++和Java语言开发的22个实际故障项目上,采用跨工程的形式训练错误定位模型。实验结果表明,新方法比最优SBFL减少了37.1%的最坏策略EXAM和22.6%的平均策略EXAM。还比较了程序语句的3类轻量级特征：结构化类别、变量谱和静态属性。新方法的时间复杂度低,能实时地推荐可能出现故障的语句序列。     

Measuring complexity in structured vs unstructured cobol programs

Measuring programmer productivity and estimating programming time and costs are among the most worrisome and persistent problems facing the programming manager. A key element in both problem areas is program complexity. It has been demonstrated in practice that a measure of program complexity is an indispensable aid in evaluating a programming effort. The purpose of this paper is to present a prototype for a composite measure of program complexity. The paper presents a basis for a technique upon which an objective quantitative evaluation for any program or programming effort could be made.This index of complexity would give the manager a tool for a quantitative assessment of programming efforts so that judgments about the relative merits of programs and programmers can be based on objective data and an objective measure. The measure is applied against a reference group of COBOL programs, several of which were written in a structured programming environment. The index of complexity and the data from which it is derived are used to evaluate the complexity of structured vs unstructured COBOL programming styles.     

基于GCC关键变量数据流分析算法的程序切片技术

随着程序的规模的扩大和复杂度的提高,通过直接分析源码进行程序切片,变得十分困难。在现有的利用编译优化技术来优化程序切片的方法中,存在无法有效利用程序的编译时信息和编译器的优化技术,以及对语言的支持不完善的问题。为此,分析了GCC编译器在编译时的中间表示,首次提出了基于GCC关键变量数据流分析算法的程序切片技术,以程序的GIMPLE中间表示为基础,以程序基本块为单位,通过迭代求解数据流方程,分析程序基本块内和不同基本块间的关键变量数据流信息。该程序切片技术可以获取源程序中仅与预设目标函数相关的关键变量和关键语句,缩减程序规模。最后通过实验,证明了该算法的可行性。     

Program Complexity and Programmer Productivity

This paper proposes a measure of program control complexity from an information theory viewpoint. A set of empirical data showing programmer productivity as a function of program control complexity is also presented. The data reveals a step-function-like contour to programmer productivity with increasing program control complexity.     

SOLMAR—A computer language for utilizing sonar models

A general high-level users' language for the convenient operation of sonar models is described. It allows the comparison of models and facilitates new model developments. The main features are: a complete default value system for all parameters, an adaptive level of complexity of the program statements, and easy access to data banks.     

Computation of logical effort in high level languages

A new measure of software complexity is introduced, that of logical effort. This measure is an attempt to quantify program complexity by an analysis of the control structure of the program, using the concepts of language virtuality and segment independence. A program is decomposed by the use of these concepts until measurements can be made at the statement level. These measurements, along with measurements of I, the effort necessary to perform a loop, and Q, the effort necessary to determine which branch to take in a decision, are then used to calculate recursively the effort in larger and larger structures, until the program level is reached. An example of this process is given for a short program, along with a brief comparison of the results obtained with a similar measure, that of cyclomatic complexity.

Algorithms for the computation of I and Q are also given, along with examples of their calculation. This process is essentially a decomposition of a Boolean function into disjunctive normal form, followed by a minimization of the form using a weighting measure involving weights on both the operators and the variables in the function.     

Several results in program size complexity

Intuitively, the program size complexity of a binary string measures the amount of information in the string. Researchers have formalized this notion in a number of different ways. Here, we demonstrate similarities between some of these formulations. We also investigate in some detail the properties of Kolmogorov's complexity measure.     

软件复杂性度量系统的研制

结合软件复杂性度量的各种算法 ,对我们自行研制开发的一种软件复杂性度量系统 (SCES)进行了详细介绍 ,并将该系统与已有的各种度量工具进行了分析比较。     

一种软件复杂性度量系统的设计与实现

本文结合软件复杂性度量的多种算法,对我们研制开发的一个软件复杂性度量系统,进行了详细介绍,并将系统与已有的各种度量工具进行了分析比较。     

Measuring dynamic program complexity

A relative complexity technique that combines the features of many complexity metrics to predict performance and reliability of a computer program is presented. Relative complexity aggregates many similar metrics into a linear compound metric that describes a program. Since relative complexity is a static measure, it is expanded by measuring relative complexity over time to find a program's functional complexity. It is shown that relative complexity gives feedback on the same complexity domains that many other metrics do. Thus, developers can save time by choosing one metric to do the work of many