We propose a data-driven algorithm for numerical invariant synthesis and verification. The algorithm is based on the ICE-DT schema for learning decision trees from samples that include positive and negative states and additionally implications corresponding to transitions in the program. The main issue we address is the discovery of relevant attributes to be used in the learning process of numerical invariants. We define a method for solving this problem that is guided by the data sample. It is based on the construction of a separator that covers positive states without including negative ones, and that is consistent with the implications. The separator is constructed using an abstract domain representation of convex sets. The generalization mechanism of the decision tree learning from the constraints of the separator allows the inference of general invariants, yet accurate enough for proving the targeted property. We implemented our algorithm and showed its efficiency.
翻译:我们提出一个数据驱动算法,用于数字变异合成和核实。算法基于ICE-DT的模型,从样本中学习决策树,包括正负状态和与程序转型相应的额外影响。我们处理的主要问题是发现相关属性,用于数字变异物的学习过程。我们定义了一种由数据样本指导的解决这一问题的方法。它基于一个分离器的构造,它涵盖正态,不包括负状态,并且与影响相一致。分隔器的构造使用同系物组合的抽象域表示方式。决定树从分离器的限制中学习的一般机制允许一般变异物的推论,但准确程度足以证明目标属性。我们应用了我们的算法并展示了它的效率。