基于二分决策图的特征模型验证方法

BDD-Based Approach to the Verification of Feature Models

特征模型是领域分析活动产生的具有复用价值的软件需求模型.对特征模型的复用通常采用定制的方式.特征模型定制中的一个重要问题是验证问题.该问题的存在是因为特征之间往往具有一定的约束关系,而一个合法的定制结果必须保证特征之间所有约束关系的被满足性.由于特征模型验证问题NP-hard所具有的性质,如何高效地进行特征模型的验证就成为一件相对困难的事情.在深入挖掘特征模型验证问题特殊性的基础上,将这种特殊性和二分决策图的结构特点进行了有效的结合,提出了一种通过对二分决策图的一次遍历即能实现特征模型验证的方法.需要指出的是,该方法并非试图在一般意义上解决特征模型验证问题中NP-hard的困难性,而是尽可能地利用该问题的特殊性,以提高处理特征模型定制问题的规模和效率.实验数据表明,相比较以前采用的验证方法,基于BDD(binary decision diagram)的方法在处理特征模型验证问题的规模和效率上都具有显著的提高.

The feature model is a reusable requirements model generated from the domain analysis. The reuse of feature models is usually achieved by a customizing-based approach. One important issue in feature models＇ customization is the verification problem, caused by the fact that there are usually constraints among features, and that a valid customizing result must satisfy all these constraints. Because of the NP-hard nature of this problem, it is usually difficult to verify feature models in an efficient way. This paper presents a BDD （binary decision diagram）-based approach to verifying feature models by only traversing once to the nodes in BDDs, an approach that makes an efficient use of the BDD data structures based on the unique characteristics of feature models＇ verification. It should be pointed out that this approach does not attempt to resolve the NP-hard difficulty of the verification problem in a general sense, but just tries to improve the scalability and efficiency of methods for feature models＇ verification based on the utilization of this problem＇s uniqueness. Experimental results show that this BDD-based approach is more efficient and can verify more complex feature models than the previous method.