H-GRASP：一种基于GRASP改进的混合SAT解法器*

为了改善GRASP的局限性,提出了一种能解决含有伪布尔（PB）和合取范式（CNF）混合约束问题的新的混合算法（H-GRASP）。该新算法采用了切削平面技术来提取PB约束条件之间的推论,并把它结合到普通的蕴涵图中,分析引起冲突的学习。与解决混合约束问题的其他两种方法——整数线性规划和纯基于SAT方法进行了彻底的比较。实验结果证明,H-GRASP方法从整体上大大减少了运行时间,加快了速度,同时还保证了加入这种方法的低耗费。     

基于子句的动态检查强制文字的SAT求解器

检查强制文字是一种重要的预处理方法。结合学习子句,提出一种在求解过程中使用的策略—基于子句的动态检查强制文字(CNL),并且设计了一种易实现低成本的数据结构。分别实现了两个不同版本的求解器:Glucose_PRE和Glucose_CNL,前者在求解初始时将检查强制文字作为预处理,后者实现了基于子句的动态检查强制文字策略。实验测试结果表明,与Glucose_PRE和Glucose3.0求解器相比,求解器Glucose_CNL在求解2015年和2016年SAT竞赛的应用类型的实例时,求解实例个数更多,耗时更少,说明所提策略和所设计的数据结构均可提高求解器的求解性能。     

An interval-based SAT modulo ODE solver for model checking nonlinear hybrid systems

This paper presents a bounded model checking tool called Hydlogic{\texttt{Hydlogic}} for hybrid systems. It translates a reachability problem of a nonlinear hybrid system into a predicate logic formula involving arithmetic constraints and checks the satisfiability of the formula based on a satisfiability modulo theories method. We tightly integrate (i) an incremental SAT solver to enumerate the possible sets of constraints and (ii) an interval-based solver for hybrid constraint systems (HCSs) to solve the constraints described in the formulas. The HCS solver verifies the occurrence of a discrete change by using a set of boxes to enclose continuous states that may cause the discrete change. We utilize the existence property of a unique solution in the boxes computed by the HCS solver as (i) a proof of the reachability of a model and (ii) a guide in the over-approximation refinement procedure. Our Hydlogic{\texttt{Hydlogic}} implementation successfully handled several examples including those with nonlinear constraints.     

Empirical evaluations on the cost-effectiveness of state-based testing: An industrial case study

ContextTest models describe the expected behavior of the software under test and provide the basis for test case and oracle generation. When test models are expressed as UML state machines, this is typically referred to as state-based testing (SBT). Despite the importance of being systematic while testing, all testing activities are limited by resource constraints. Thus, reducing the cost of testing while ensuring sufficient fault detection is a common goal in software development. No rigorous industrial case studies of SBT have yet been published.ObjectiveIn this paper, we evaluate the cost-effectiveness of SBT on actual control software by studying the combined influence of four testing aspects: coverage criterion, test oracle, test model and unspecified behavior (sneak paths).MethodAn industrial case study was used to investigate the cost-effectiveness of SBT. To enable the evaluation of SBT techniques, a model-based testing tool was configured and used to automatically generate test suites. The test suites were evaluated using 26 real faults collected in a field study.ResultsResults show that the more detailed and rigorous the test model and oracle, the higher the fault-detection ability of SBT. A less precise oracle achieved 67% fault detection, but the overall cost reduction of 13% was not enough to make the loss an acceptable trade-off. Removing details from the test model significantly reduced the cost by 85%. Interestingly, only a 24–37% reduction in fault detection was observed. Testing for sneak paths killed the remaining eleven mutants that could not be killed by the conformance test strategies.ConclusionsEach of the studied testing aspects influences cost-effectiveness and must be carefully considered in context when selecting strategies. Regardless of these choices, sneak-path testing is a necessary step in SBT since sneak paths are common while also undetectable by conformance testing.     

基于不完全算法的并行FPGA SAT求解器

可满足性问题是计算机理论与应用的核心问题。在FPGA上提出了一个基于不完全算法的并行求解器pprobSAT+。使用多线程的策略来减少相关组件的等待时间,提高了求解器效率。此外,不同线程采用共用地址和子句信息的数据存储结构,以减少片上存储器的资源开销。当所有数据均存储在FPGA的片上存储器时,pprobSAT+求解器可以达到最佳性能。实验结果表明,相比于单线程的求解器,所提出的pprobSAT+求解器可获得超过2倍的加速比。     

基于回跳层数的SAT求解器学习子句删除策略

目前学习子句删除策略广泛采用的是基于LBD的评估方式,LBD评估方式在每次执行删除时都会删除前一半LBD值大的学习子句,这种方式对LBD值大的学习子句的删除过于激进。针对此问题,提出了一种利用冲突回跳层数（back-jump levels）的评估方式来保留LBD值较大的相关学习子句。以CDCL（conflict driven clause learning）完备算法为框架,在子句删除环节形成了BJL删除算法。通过测试2017年SAT国际竞赛例,对新改进的版本与原版求解器进行了对比实验。实验表明,所提策略可显著提高求解器的求解性能和求解效率。     

Sustainable supply chain optimisation: An industrial case study

Sustainability plays a key role in the management of a successful and responsible business. When trying to improve the sustainability performance of a business, there are three major challenges that need to be addressed. First, assessment of sustainability requires consideration of not just economic, but also environmental and social impacts. Second, we need to find appropriate sustainability indicators and gather the necessary data in order to quantify sustainability performance. Finally, sustainability has to be seen in the context of the whole system, i.e. it has to include all activities along the supply chain. In this work, we consider all three aspects and propose a multi-objective optimisation framework for the optimisation of a sustainable supply chain. Three sustainability indicators have been considered, namely the total cost, GHG emissions and lead time. We apply this framework to an industrial test case using real-world data drawn from a Dow Chemical business. The results show clear trade-offs between the three different objectives. However, we can also observe that typically a considerable decrease in GHG emissions or lead time can already be achieved by only a relatively small increase in cost. The proposed framework enables us to determine such trade-off relations and consequently make decisions that improve the sustainability performance of the supply chain.     

UnitWalk: A new SAT solver that uses local search guided by unit clause elimination

In this paper we present a new randomized algorithm for SAT, i.e., the satisfiability problem for Boolean formulas in conjunctive normal form. Despite its simplicity, this algorithm performs well on many common benchmarks ranging from graph coloring problems to microprocessor verification. Our algorithm is inspired by two randomized algorithms having the best current worst-case upper bounds ([27,28] and [30,31]). We combine the main ideas of these algorithms in one algorithm. The two approaches we use are local search (which is used in many SAT algorithms, e.g., in GSAT [34] and WalkSAT [33]) and unit clause elimination (which is rarely used in local search algorithms). In this paper we do not prove any theoretical bounds. However, we present encouraging results of computational experiments comparing several implementations of our algorithm with other SAT solvers. We also prove that our algorithm is probabilistically approximately complete (PAC).     

UnitWalk: A new SAT solver that uses local search guided by unit clause elimination

In this paper we present a new randomized algorithm for SAT, i.e., the satisfiability problem for Boolean formulas in conjunctive normal form. Despite its simplicity, this algorithm performs well on many common benchmarks ranging from graph coloring problems to microprocessor verification. Our algorithm is inspired by two randomized algorithms having the best current worst-case upper bounds ([27,28] and [30,31]). We combine the main ideas of these algorithms in one algorithm. The two approaches we use are local search (which is used in many SAT algorithms, e.g., in GSAT [34] and WalkSAT [33]) and unit clause elimination (which is rarely used in local search algorithms). In this paper we do not prove any theoretical bounds. However, we present encouraging results of computational experiments comparing several implementations of our algorithm with other SAT solvers. We also prove that our algorithm is probabilistically approximately complete (PAC).     

Vibrometry of industrial workers: A case study

Vibrometry was performed on 165 factory workers and supervisors in 18 different job classifications. A low vibrometry score indicates insensitivity to vibrations and thus potential compression neuropathy. Males had significantly higher scores than females. Subjective estimates of the job's repetitiveness, force requirement and wrist angle movement did not correlate significantly with the vibrometry score but pace did (self-paced jobs had higher scores). Questions relating to pain in the hands and numbness in the hands were significant predictors of the score. The conventional vibrometry score is the total from seven frequencies. Analysis shows only the top frequencies (125, 250, 500 Hz) are needed and possibly just 250 and 500 Hz.     

Software generated device exception for more intensive device-related software testing: An industrial field study

It is more important to properly handle exceptions, than to prevent exceptions from occurring, because they arise from so many different causes. In embedded systems, a vast number of exceptions are caused by hardware devices. In such cases, numerous software components are involved in these hardware device-originated exceptions, ranging from the device itself to the device driver, the kernel, and applications. Therefore, it takes a lot of time to debug software that fails to handle exceptions. This paper proposes a lightweight device exception testing method, and a related automation tool, AMOS v3.0. The proposed method artificially triggers more realistic device exceptions in runtime, and monitors how software components handle exceptions in detail. AMOS v3.0 has been applied to the exception testing of car-infotainment systems in an automobile company. The results based on this industrial field study have revealed that 39.13% of the failures in exception handling were caused by applications, 36.23% of the failures were caused by device drivers, and 24.64% were derived from the kernel. We conclude that the proposed method is highly effective, in that it can allow developers to identify the root cause of failure for exception handling.     

An industrial case study in reconstructing requirements views

Requirements views, such as coverage and status views, are an important asset for monitoring and managing software development projects. We have developed a method that automates the process of reconstructing these views, and we have built a tool, ReqAnalyst, that supports this method. This paper presents an investigation as to which extent requirements views can be automatically generated in order to monitor requirements in industrial practice. The paper focuses on monitoring the requirements in test categories and test cases. In order to retrieve the necessary data, an information retrieval technique, called Latent Semantic Indexing, was used. The method was applied in an industrial study. A number of requirements views were defined and experiments were carried out with different reconstruction settings for generating these views. Finally, we explored how these views can help the developers during the software development process.

Formal specification and testing: A case study

Z is a formal notation for writing system specifications that has been growing in popularity over recent years. This paper examines some of the issues involved in applying a ‘partition based’ testing method to a system specified in Z. Details of an extensive case study are given, from specification and implementation of the system to the development and execution of test cases. The strategy is found to have benefits compared to those based on less formal specifications, but there are limitations to the approach, and difficulties that need addressing.     

An industrial case study of classifier ensembles for locating software defects

As the application layer in embedded systems dominates over the hardware, ensuring software quality becomes a real challenge. Software testing is the most time-consuming and costly project phase, specifically in the embedded software domain. Misclassifying a safe code as defective increases the cost of projects, and hence leads to low margins. In this research, we present a defect prediction model based on an ensemble of classifiers. We have collaborated with an industrial partner from the embedded systems domain. We use our generic defect prediction models with data coming from embedded projects. The embedded systems domain is similar to mission critical software so that the goal is to catch as many defects as possible. Therefore, the expectation from a predictor is to get very high probability of detection (pd). On the other hand, most embedded systems in practice are commercial products, and companies would like to lower their costs to remain competitive in their market by keeping their false alarm (pf) rates as low as possible and improving their precision rates. In our experiments, we used data collected from our industry partners as well as publicly available data. Our results reveal that ensemble of classifiers significantly decreases pf down to 15% while increasing precision by 43% and hence, keeping balance rates at 74%. The cost-benefit analysis of the proposed model shows that it is enough to inspect 23% of the code on local datasets to detect around 70% of defects.     

Automated discovery of local search heuristics for satisfiability testing

The development of successful metaheuristic algorithms such as local search for a difficult problem such as satisfiability testing (SAT) is a challenging task. We investigate an evolutionary approach to automating the discovery of new local search heuristics for SAT. We show that several well-known SAT local search algorithms such as Walksat and Novelty are composite heuristics that are derived from novel combinations of a set of building blocks. Based on this observation, we developed CLASS, a genetic programming system that uses a simple composition operator to automatically discover SAT local search heuristics. New heuristics discovered by CLASS are shown to be competitive with the best Walksat variants, including Novelty+. Evolutionary algorithms have previously been applied to directly evolve a solution for a particular SAT instance. We show that the heuristics discovered by CLASS are also competitive with these previous, direct evolutionary approaches for SAT. We also analyze the local search behavior of the learned heuristics using the depth, mobility, and coverage metrics proposed by Schuurmans and Southey.     

On the long-term use of visual gui testing in industrial practice: a case study

Visual GUI Testing (VGT) is a tool-driven technique for automated GUI-based testing that uses image recognition to interact with and assert the correctness of the behavior of a system through its GUI as it is shown to the user. The technique’s applicability, e.g. defect-finding ability, and feasibility, e.g. time to positive return on investment, have been shown through empirical studies in industrial practice. However, there is a lack of studies that evaluate the usefulness and challenges associated with VGT when used long-term (years) in industrial practice. This paper evaluates how VGT was adopted, applied and why it was abandoned at the music streaming application development company, Spotify, after several years of use. A qualitative study with two workshops and five well chosen employees is performed at the company, supported by a survey, which is analyzed with a grounded theory approach to answer the study’s three research questions. The interviews provide insights into the challenges, problems and limitations, but also benefits, that Spotify experienced during the adoption and use of VGT. However, due to the technique’s drawbacks, VGT has been abandoned for a new technique/framework, simply called the Test interface. The Test interface is considered more robust and flexible for Spotify’s needs but has several drawbacks, including that it does not test the actual GUI as shown to the user like VGT does. From the study’s results it is concluded that VGT can be used long-term in industrial practice but it requires organizational change as well as engineering best practices to be beneficial. Through synthesis of the study’s results, and results from previous work, a set of guidelines are presented that aim to aid practitioners to adopt and use VGT in industrial practice. However, due to the abandonment of the technique, future research is required to analyze in what types of projects the technique is, and is not, long-term viable. To this end, we also present Spotify’s Test interface solution for automated GUI-based testing and conclude that it has its own benefits and drawbacks.     

Usage and usefulness of technical software documentation: An industrial case study

ContextSoftware documentation is an integral part of any software development process. However, software practitioners are often concerned about the value, degree of usage and usefulness of documentation during development and maintenance.ObjectiveMotivated by the needs of NovAtel Inc. (NovAtel), a world-leading company developing software systems in support of global navigation satellite systems, and based on the results of a former systematic mapping study, we aimed at better understanding of the usage and the usefulness of various technical documents during software development and maintenance.MethodWe utilized the results of a former systematic mapping study and performed an industrial case study at NovAtel. From the joint definition of the analysis goals, the research method incorporates qualitative and quantitative analysis of 55 documents (design, test and process related) and 1630 of their revisions. In addition, we conducted a survey on the usage and usefulness of documents. A total of 25 staff members from the industrial partner, all having a medium to high level of experience, participated in the survey.ResultsIn the context of the case study, a number of findings were derived. They include that (1) technical documentation was consulted least frequently for maintenance purpose and most frequently as an information source for development, (2) source code was considered most frequently as the preferred information source during software maintenance, (3) there is no significant difference between the usage of various documentation types during both development and maintenance, and (4) initial hypotheses stating that up-to-date information, accuracy and preciseness have the highest impact on usefulness of technical documentation.ConclusionsIt is concluded that the usage of documentation differs for various purposes and it depends on the type of the information needs as well as the tasks to be completed (e.g., development and maintenance). The results have been confirmed to be helpful for the company under study, and the firm is currently implementing some of the recommendations given.     

Local Search Algorithms for SAT: An Empirical Evaluation

Local search algorithms are among the standard methods for solving hard combinatorial problems from various areas of artificial intelligence and operations research. For SAT, some of the most successful and powerful algorithms are based on stochastic local search, and in the past 10 years a large number of such algorithms have been proposed and investigated. In this article, we focus on two particularly well-known families of local search algorithms for SAT, the GSAT and WalkSAT architectures. We present a detailed comparative analysis of these algorithms" performance using a benchmark set that contains instances from randomized distributions as well as SAT-encoded problems from various domains. We also investigate the robustness of the observed performance characteristics as algorithm-dependent and problem-dependent parameters are changed. Our empirical analysis gives a very detailed picture of the algorithms" performance for various domains of SAT problems; it also reveals a fundamental weakness in some of the best-performing algorithms and shows how this can be overcome.     

A note on width-parameterized SAT: An exact machine-model characterization

We characterize the complexity of SAT instances with path-decompositions of width w(n). Although pathwidth is the most restrictive among the studied width-parameterizations of SAT, the most time-efficient algorithms known for such SAT instances run in time ²Ω(w(n)), even when the path-decomposition is given in the input. We wish to better understand the decision complexity of SAT instances of width ω(logn). We provide an exact correspondence between SATpw[w(n)], the problem of SAT instances with given path decomposition of width w(n), and NL[r(n)], the class of problems decided by logspace Turing Machines with at most r(n) passes over the nondeterministic tape. In particular, we show that SATpw[w(n)] is hard for under log-space reductions. When is closed under logspace reductions, which is the case for the most interesting w(n)'s, we show that SATpw[w(n)] is also complete.