Neural implicit functions including signed distance functions (SDFs) and unsigned distance functions (UDFs) have shown powerful ability in fitting the shape geometry. However, inferring continuous distance fields from discrete unoriented point clouds still remains a challenge. The neural network typically fits the shape with a rough surface and omits fine-grained geometric details such as shape edges and corners. In this paper, we propose a novel non-linear implicit filter to smooth the implicit field while preserving high-frequency geometry details. Our novelty lies in that we can filter the surface (zero level set) by the neighbor input points with gradients of the signed distance field. By moving the input raw point clouds along the gradient, our proposed implicit filtering can be extended to non-zero level sets to keep the promise consistency between different level sets, which consequently results in a better regularization of the zero level set. Since the unsigned distance function is non-differentiable at the zero level set and lacks a stable gradient field, we further propose a gradient immutable training schema to migrate the filter to the unsigned distance function learned from point clouds. By leveraging the UDF training schema, we also improve sparse-view reconstruction results. We conduct comprehensive experiments in surface reconstruction from objects, complex scene point clouds, and multi-view images, and we further extend to the point normal estimation and point cloud upsampling tasks. The numerical and visual comparisons demonstrate our improvements over the state-of-the-art methods under the widely used benchmarks.

Recently, Gaussian Splatting has sparked a new trend in the field of computer vision. Apart from novel view synthesis, it has also been extended to the area of multi-view reconstruction. The latest methods facilitate complete, detailed surface reconstruction while ensuring fast training speed. However, these methods still require dense input views, and their output quality significantly degrades with sparse views. We observed that the Gaussian primitives tend to overfit the few training views, leading to noisy floaters and incomplete reconstruction surfaces. In this paper, we present an innovative sparse-view reconstruction framework that leverages intra-view depth and multi-view feature consistency to achieve remarkably accurate surface reconstruction. Specifically, we utilize monocular depth ranking information to supervise the consistency of depth distribution within patches and employ a smoothness loss to enhance the continuity of the distribution. To achieve finer surface reconstruction, we optimize the absolute position of depth through multi-view projection features. Extensive experiments on DTU and BlendedMVS demonstrate that our method outperforms state-of-the-art methods with a speedup of 60x to 200x, achieving swift and fine-grained mesh reconstruction without the need for costly pre-training.

In recent years, reconstructing indoor scene geometry from multi-view images has achieved encouraging accomplishments. Current methods incorporate monocular priors into neural implicit surface models to achieve high-quality reconstructions. However, these methods require hundreds of images for scene reconstruction. When only a limited number of views are available as input, the performance of monocular priors deteriorates due to scale ambiguity, leading to the collapse of the reconstructed scene geometry. In this paper, we propose a new method, named Sparis, for indoor surface reconstruction from sparse views. Specifically, we investigate the impact of monocular priors on sparse scene reconstruction, introducing a novel prior based on inter-image matching information. Our prior offers more accurate depth information while ensuring cross-view matching consistency. Additionally, we employ an angular filter strategy and an epipolar matching weight function, aiming to reduce errors due to view matching inaccuracies, thereby refining the inter-image prior for improved reconstruction accuracy. The experiments conducted on widely used benchmarks demonstrate superior performance in sparse-view scene reconstruction.

Recently, neural implicit functions have demonstrated remarkable results in the field of multi-view reconstruction. However, most existing methods are tailored for dense views and exhibit unsatisfactory performance when dealing with sparse views. Several latest methods have been proposed for generalizing implicit reconstruction to address the sparse view reconstruction task, but they still suffer from high training costs and are merely valid under carefully selected perspectives. In this paper, we propose a novel sparse view reconstruction framework that leverages on-surface priors to achieve highly faithful surface reconstruction. Specifically, we design several constraints on global geometry alignment and local geometry refinement for jointly optimizing coarse shapes and fine details. To achieve this, we train a neural network to learn a global implicit field from the on-surface points obtained from SfM and then leverage it as a coarse geometric constraint. To exploit local geometric consistency, we project on-surface points onto seen and unseen views, treating the consistent loss of projected features as a fine geometric constraint. The experimental results with DTU and BlendedMVS datasets in two prevalent sparse settings demonstrate significant improvements over the state-of-the-art methods.

Implicit neural networks have emerged as a crucial technology in 3D surface reconstruction. To reconstruct continuous surfaces from discrete point clouds, encoding the input points into regular grid features (plane or volume) has been commonly employed in existing approaches. However, these methods typically use the grid as an index for uniformly scattering point features. Compared with the irregular point features, the regular grid features may sacrifice some reconstruction details but improve efficiency. To take full advantage of these two types of features, we introduce a novel and high-efficiency attention mechanism between the grid and point features named Point-Grid Transformer (GridFormer). This mechanism treats the grid as a transfer point connecting the space and point cloud. Our method maximizes the spatial expressiveness of grid features and maintains computational efficiency. Furthermore, optimizing predictions over the entire space could potentially result in blurred boundaries. To address this issue, we further propose a boundary optimization strategy incorporating margin binary cross-entropy loss and boundary sampling. This approach enables us to achieve a more precise representation of the object structure. Our experiments validate that our method is effective and outperforms the state-of-the-art approaches under widely used benchmarks by producing more precise geometry reconstructions. The code is available at https://github.com/list17/GridFormer.

Delays are inevitable in complex distributed environments. Timeout mechanisms are commonly used to handle unexpected failures in distributed systems. However, incorrect timeout handling or implementation errors in timeout mechanisms can lead to system hang-ups or crashes. Such timeout bugs may be crucial and pose a significant threat to the availability and security of distributed systems.In this work, we introduce Chronos, a general testing framework for automatically detecting timeout bugs in distributed systems with deep-priority transient delays. First, we propose general runtime delayed libraries that dynamically inject fine-grained delays in a Distributed System Under Test (DSUT). To effectively trigger delays and constantly explore timeout bugs in deep paths, Chronos harnesses a deep-priority guided fuzzing that dynamically generates high-quality delay sequences in the runtime. Then, Chronos utilizes transient delays to eliminate the time overhead caused by actual delays and accelerate the test process. We implemented and evaluated Chronos on four widely used distributed systems, including ZooKeeper, MySQL-Cluster, HDFS, and Go-Ethereum. Compared with the state-of-the-art techniques, Random, Brute-Force, and Coverage-Guided fault injection, Chronos covers 26.40%, 21.69%, and 15.14% more timeout mechanism logic, respectively. Furthermore, Chronos has detected 27 timeout bugs in these real-world applications, which have been repaired by the corresponding maintainers.

Biru Zhu, Lifan Yuan, Ganqu Cui, Yangyi Chen, Chong Fu, Bingxiang He, Yangdong Deng, Zhiyuan Liu, Maosong Sun, Ming Gu. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

Abstract Recent research has revealed that pre-trained models (PTMs) are vulnerable to backdoor attacks before the fine-tuning stage. The attackers can implant transferable task-agnostic backdoors in PTMs, and control model outputs on any downstream task, which poses severe security threats to all downstream applications. Existing backdoor-removal defenses focus on task-specific classification models and they are not suitable for defending PTMs against task-agnostic backdoor attacks. To this end, we propose the first task-agnostic backdoor removal method for PTMs. Based on the selective activation phenomenon in backdoored PTMs, we design a simple and effective backdoor eraser, which continually pre-trains the backdoored PTMs with a regularization term in an end-to-end approach. The regularization term removes backdoor functionalities from PTMs while the continual pre-training maintains the normal functionalities of PTMs. We conduct extensive experiments on pre-trained models across different modalities and architectures. The experimental results show that our method can effectively remove backdoors inside PTMs and preserve benign functionalities of PTMs with a few downstream-task-irrelevant auxiliary data, e.g., unlabeled plain texts. The average attack success rate on three downstream datasets is reduced from 99.88% to 8.10% after our defense on the backdoored BERT. The codes are publicly available at https://github.com/thunlp/RECIPE.

Biru Zhu, Yujia Qin, Fanchao Qi, Yangdong Deng, Zhiyuan Liu, Maosong Sun, Ming Gu. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022.

The Combinatorial optimization problem (COP) such as Traveling Salesman Problem (TSP) is widely used in various industries such as manufacturing, transportation, logistics and express delivery, etc. Deep reinforcement learning is the latest approach to solving the TSP. The policy gradient approach is an efficient and effective method to tackle the TSP, where critic and rollout baselines are often used. However, these baselines increase training time and memory space usage during the training process, and the training efficiency is not high. Therefore, this paper proposes a new baseline, Random Baseline, randomly selecting float numbers as a baseline from a range. Using a set of node coordinates as the input, we train a Long Short-Term Memory (LSTM) network to predict a distribution over city permutations, utilizing negative tour length as the reward, and optimizing the LSTM network parameters using a policy gradient with Random Baseline. The extensive experiments comparing the existing baselines demonstrate that the training time is reduced by 16% on average in Euclidean 2D TSP20, TSP50, and TSP100 tasks, on 1200000 training instances, respectively.

Despite the great success of pre-trained language models (PLMs) in a large set of natural language processing (NLP) tasks, there has been a growing concern about their security in real-world applications. Backdoor attack, which poisons a small number of training samples by inserting backdoor triggers, is a typical threat to security. Trained on the poisoned dataset, a victim model would perform normally on benign samples but predict the attacker-chosen label on samples containing pre-defined triggers. The vulnerability of PLMs under backdoor attacks has been proved with increasing evidence in the literature. In this paper, we present several simple yet effective training strategies that could effectively defend against such attacks. To the best of our knowledge, this is the first work to explore the possibility of backdoor-free adaptation for PLMs. Our motivation is based on the observation that, when trained on the poisoned dataset, the PLM's adaptation follows a strict order of two stages: (1) a moderate-fitting stage, where the model mainly learns the major features corresponding to the original task instead of subsidiary features of backdoor triggers, and (2) an overfitting stage, where both features are learned adequately. Therefore, if we could properly restrict the PLM's adaptation to the moderate-fitting stage, the model would neglect the backdoor triggers but still achieve satisfying performance on the original task. To this end, we design three methods to defend against backdoor attacks by reducing the model capacity, training epochs, and learning rate, respectively. Experimental results demonstrate the effectiveness of our methods in defending against several representative NLP backdoor attacks. We also perform visualization-based analysis to attain a deeper understanding of how the model learns different features, and explore the effect of the poisoning ratio. Finally, we explore whether our methods could defend against backdoor attacks for the pre-trained CV model. The codes are publicly available at https://github.com/thunlp/Moderate-fitting.

Precise static analysis is necessary for an industrial environment to ensure reliability and security, which is usually field-sensitive and inter-procedural. However, it faces the problem of insufficient scale capability when being applied to various industrial environments: (1) Field-sensitive analysis can not assure termination if field accesses are modeled by unbounded access paths; (2) Inter-procedural analysis may lead to path explosion problems because of the unbounded length of call chains. While using longer access paths or call chains can improve precision, the analysis may have poor performance in terms of efficiency. Specifically, an industry-strength method should be scalable enough to face different applications. This paper presents a scalable fault detection method based on the precise access path. Precise access path models a memory location with accurate operations and offsets from a source. Points-to relations of variables are used to refine it. It can differentiate elements of aggregate structures and is more precise than the ordinary access path. Based on the precise access path, we perform an inter-procedural analysis with the help of an intra-procedural analysis and combined function summary. Furthermore, our method is designed backward to detect error handling bugs. Compared with the state-of-the-art tools, our method is more scalable, with higher precision and efficiency on both benchmarks and 11 widely-used applications.

SSL library plays an important role in ensuring secure connections against remote attacks, and thus the correct usages of SSL library should be guaranteed to avoid security and reliability flaws. However, improper error handling of API function failures frequently happens in SSL library usages, which could introduce security vulnerabilities. To detect such bugs in SSL usages, existing tools need correct error handling specifications. Manually write specifications is tedious and time-consuming. Therefore, a few works towards automatic inferring specifications are presented. However, the principles used in such works are insufficient for SSL library. Thus, in this paper, we first conduct an empirical study of error handling bugs in SSL applications to understand the true nature of such bugs, and the properties of these bugs are summarized, including the frequently used code structure for handling errors, the commonly occurred error-indicating features of the handling actions, and the general bug categories. Based on these properties, we design and implement a tool that can automatically infer error handling specifications and detect error handling bugs by exploiting the specifications in SSL applications. We evaluated our tool on 9 real-world open-source SSL applications. The tool infers 424 specifications in total, out of which 383 are confirmed correct, with a precision of 90%. Moreover, 27 real-world bugs have been detected, and all of them are confirmed by developers.

As the Internet and social media offer increasing opportunities for organizations and individuals to publicize online contents, it has become essential to develop effective means to identify misinformation like fake news. Recently, fact checking systems have been regarded as a promising tool to automatically deal with large amounts of information. How to effectively take advantage of existing unstructured document knowledge bases and structured knowledge graphs to build robust fact checking systems, however, remains to be a challenge. In this paper, we propose a knowledge enhanced fact checking system, which leverages the Wikidata5M knowledge graph and Wikipedia documents to incorporate external knowledge into the claim to be checked for more robust and accurate fact checking. First, we devise a contextualized knowledge graph selection method to identify the most relevant sub-graph with the checked claim from the large knowledge graph. We then construct a novel claim-evidence-knowledge graph and use a graph attention network to integrate natural language evidence with structured knowledge triplets by allowing them to propagate information among each other. By integrating the claim, retrieved evidence and selected knowledge triplets in a unified claim-evidence-knowledge graph, our method improves the label accuracy of predicted claims by more than 4% on the FEVER dataset over state-of-the-art fact checking models.

C language plays a key role in system programming and applications. Integer error is a common yet important C program defect because arithmetic operations may produce unrepresentable values in certain integer types. Integer error is one of the major sources of software failures and vulnerabilities. Due to the complex semantics of C integers, manually repairing integer errors is prone to introducing additional errors even for experienced programmers. This paper presents an approach to automatically generate fixes for integer errors. Our approach infers, for each expression, a type that is capable of representing its possible values, and utilizes inferred types as program fixes based on common fix patterns codified from real world. We have developed our system IntPTI which is evaluated on the largest public benchmark of integer errors and 7 widely-used open-source projects. The evaluation results demonstrate the superior performance of IntPTI in terms of accuracy, scalability, runtime overhead and robustness of fixes. In addition, IntPTI is applied on the embedded software of a realistic train control system. It succeeds in both detecting 67 new integer errors and generating 101 fixes confirmed by developers. The study substantiates the feasibility and effectiveness of the proposed methodology.

With the fast digitalization of our society, mining patterns from large time series data is increasingly becoming a critical problem for a wide range of big data applications. Motif and discord discovery algorithms, which offer effective solutions to identify repeatedly appearing and abnormal patterns, respectively, are fundamental building blocks for time series processing. Both approaches, however, can be time extremely consuming when handling large time series due to the subsequence-based computations of distance similarity metrics. In this article, we show that the highly involved subsequence-based computations can actually be decomposed into a few fine-grained computing patterns for efficient data parallel computing. By developing highly efficient GPU algorithms for such basic patterns and effectively composing such patterns, we are able to solve both motif and discord discovery problems under euclidean and DTW distance metrics in a unified GPU acceleration framework. Extensive experiments prove that the proposed framework outperforms pruned CPU algorithms by up to three orders of magnitude. Our work paves the foundation of building GPU acceleration frameworks for large-scale time series datasets.

Time-sensitive networking (TSN) is a set of extended standards for the IEEE 802.3 Ethernet under development by the IEEE 802.1 TSN task group. TSN depends on two key components, scheduling and fault tolerance, to provide realtime and reliable transmission. There is a strong motivation to replace the widely used field-buses with TSNs in industrial networking applications. However, industrial network devices are typical application-specific embedded systems with limited memory resources. Time-sensitive (TS) transmission certainly prefers on-chip memory, which is even more scarce for embedded systems. As a result, it is critical for TSNs to develop memory-efficient switching techniques with scalable schedulability and elegant fault-tolerance support. This paper proposes a time-triggered switch-memory-switch (SMS) architecture for memory-efficient TSN switches. First, based on the SMS shared memory, our architecture makes it possible to statically schedule memory allocation with full utilization for TS traffic and the remaining memory for other traffic. Compared with perport memory, the shared memory achieves a ratio of (nn/n!) (≈ (en/√(2πn)), n → ∞), where n is the port number, in the feasible solution space under memory constraints and thus significantly improves scheduling memory ability and flexibility. Moreover, we develop a fault-tolerance scheme for reliable transmission. It facilitates a memory-efficient implementation of the popular multiline redundancy in industrial networks. The scheme is validated by five classes of memory conflicts and a case study on two-line redundancy.

An increasingly important trend in the design of industry-strength embedded systems is the integration of multiple services with varying criticality levels into a common computing platform. Such systems are characterized as mixed-criticality multiservice systems (MCMSs). An MCMS has to survive in rigorous environments posed by industry-level requirements. Such survival, however, is becoming continuously more challenging due to the growing system complexity and integrating more and more services. While existing works typically target reliability-driven design optimization to improve the system robustness rather than deal with the surviving problem of the system in extreme physical environments, this paper addresses the problem by enabling the service capability transitions of an MCMS to adapt to the environments. This paper proposes a service capability model to capture the importance of functional modules for the criticality of different services. A model-based service-capability transition mechanism is designed to automatically identify the maximum allowed service capability under a given physical environment. A case study of the proposed techniques was performed on an industrial Ethernet switch which is a typical MCMS, to validate the capability of adaptation to high and low temperatures. The experimental results demonstrate the significant potential of our approach to improve system survivability under extreme physical environments.

With the development of hardware virtualization and cloud computing, modern industry has a tendency to upgrade from the traditional industrial networks to virtual machine (VM) based networks. To provide firm latency guarantees for control messages in these networks, the time-sensitive network (TSN) is a promising technology due to its determinacy for real-time applications. However, TSN faces the challenge of providing a rapid response to dynamic transmission requirement changes incurred by VM migrations. In this paper, we proposed an online scheduling approach to deal with dynamic VM migrations in multicast TSN. In this approach, we devise a novel online scheduling framework [minimal distance tree (MDT) construction - heuristic breadth first search] containing an offline scheduling phase and an online rescheduling phase. While the offline phase introduces a MDT to increase reusable scheduling results, the online phase proposes a heuristic scheduling approach to reuse the results of the offline phase as much as possible to accelerate the rescheduling process. Experiments show that our framework can provide a rapid response to dynamic VM migrations compared with the existing approaches where the amount of control data does not exceed 50% of the bandwidth.

Precise pointer analysis is desired since many program analyses benefit from it both in precision and performance. There are several dimensions of pointer analysis precision, flow sensitivity, context sensitivity, field sensitivity and path sensitivity. The more dimensions a pointer analysis considers, the more accurate its results will be. However, considering all dimensions is difficult because the trade-off between precision and efficiency should be balanced. This paper presents a flow, context, field and quasi path sensitive pointer analysis algorithm for C programs. Our algorithm runs on a control flow automaton, a key structure for our analysis to be flow sensitive. During the analysis process, we use function summaries to get context information. Elements of aggregate structures are handled to improve precision. We collect path conditions to filter unreachable paths and make all points-to relations gated. For efficiency, we propose a multi-entry mechanism. The algorithm is implemented in TsmartGP, which is an extension of CPAchecker. Our algorithm is compared with some state-of-the-art algorithms and TsmartGP is compared with cppcheck and Clang Static Analyzer by detecting uninitialized pointer errors in 13 real-world applications. The experimental results show that our algorithm is more accurate and TsmartGP can find more errors than other tools.

Today, large and complex software is developed with integrated components using application programming interfaces (APIs). Correct usage of APIs in practice presents a challenge due to implicit constraints, such as call conditions or call orders. API misuse, i.e., violation of these constraints, is a well-known source of bugs, some of which can cause serious security vulnerabilities. Although researchers have developed many API-misuse detectors over the last two decades, recent studies show that API misuses are still prevalent. In this paper, we provide a comprehensive empirical study on API-misuse bugs in open-source C programs. To understand the nature of API misuses in practice, we analyze 830 API-misuse bugs from six popular programs across different domains. For all the studied bugs, we summarize their root causes, fix patterns and usage statistics. Furthermore, to understand the capabilities and limitations of state-of-the-art static analysis detectors for API-misuse detection, we develop APIMU4C, a dataset of API-misuse bugs in C code based on our empirical study results, and evaluate three widely-used detectors on it qualitatively and quantitatively. We share all the findings and present possible directions towards more powerful API-misuse detectors.

Static analysis has long prevailed as a promising approach to detect program bugs at an early development process to increase software quality. However, such tools face great challenges to balance the false-positive rate and the false-negative rate in practical use. In this paper, we present VBSAC, a value-based static analyzer for C aiming to improve the precision and recall. In our tool, we employ a pluggable value-based analysis strategy. A memory skeleton recorder is designed to maintain the memory objects as a baseline. While traversing the control flow graph, diverse value-based plug-ins analyze the specific abstract domains and share program information to strengthen the computation. Simultaneously, checkers consume the corresponding analysis results to detect bugs. We also provide a user-friendly web interface to help users audit the bug detection results. Evaluation on two widely-used benchmarks shows that we perform better to state-of-the-art bug detection tools by finding 221-339 more bugs and improving F-Score 9.88%-40.32%.

Golang (short for Go programming language) is a fast and compiled language, which has been increasingly used in industry due to its excellent performance on concurrent programming. Golang redefines concurrent programming grammar, making it a challenge for traditional clone detection tools and techniques. However, there exist few tools for detecting duplicates or copy-paste related bugs in Golang. Therefore, an effective and efficient code clone detector on Golang is especially needed.

Misuse of APIs happens frequently due to misunderstanding of API semantics and lack of documentation. An important category of API-related defects is the error handling defects, which may result in security and reliability flaws. These defects can be detected with the help of static program analysis, provided that error specifications are known. The error specification of an API function indicates how the function can fail. Writing error specifications manually is time-consuming and tedious. Therefore, automatic inferring the error specification from API usage code is preferred. In this paper, we present Ares, a tool for automatic inferring error specifications for C code through static analysis. We employ multiple heuristics to identify error handling blocks and infer error specifications by analyzing the corresponding condition logic. Ares is evaluated on 19 real world projects, and the results reveal that Ares outperforms the state-of-the-art tool APEx by 37% in precision. Ares can also identify more error specifications than APEx. Moreover, the specifications inferred from Ares help find dozens of API-related bugs in well-known projects such as OpenSSL, among them 10 bugs are confirmed by developers. Video: https://youtu.be/nf1QnFAmu8Q. Repository: https://github.com/lc3412/Ares.

Precise pointer analysis is desired since it is a core technique to find memory defects. There are several dimensions of pointer analysis precision, flow sensitivity, context sensitivity, field sensitivity and path sensitivity. For static analysis tools utilizing pointer analysis, considering all dimensions is difficult because the trade-off between precision and efficiency should be balanced. This paper presents TsmartGP, a static analysis tool for finding memory defects in C programs with a precise and efficient pointer analysis. The pointer analysis algorithm is flow, context, field, and quasi path sensitive. Control flow automatons are the key structures for our analysis to be flow sensitive. Function summaries are applied to get context information and elements of aggregate structures are handled to improve precision. Path conditions are used to filter unreachable paths. For efficiency, a multi-entry mechanism is proposed. Utilizing the pointer analysis algorithm, we implement a checker in TsmartGP to find uninitialized pointer errors in 13 real-world applications. Cppcheck and Clang Static Analyzer are chosen for comparison. The experimental results show that TsmartGP can find more errors while its accuracy is also higher than Cppcheck and Clang Static Analyzer. The demo video is available at https://youtu.be/IQlshemk6OA.

Low-rank metric learning aims to learn better discrimination of data subject to low-rank constraints. It keeps the intrinsic low-rank structure of datasets and reduces the time cost and memory usage in metric learning. However, it is still a challenge for current methods to handle datasets with both high dimensions and large numbers of samples. To address this issue, we present a novel fast low-rank metric learning (FLRML) method. FLRML casts the low-rank metric learning problem into an unconstrained optimization on the Stiefel manifold, which can be efficiently solved by searching along the descent curves of the manifold. FLRML significantly reduces the complexity and memory usage in optimization, which makes the method scalable to both high dimensions and large numbers of samples. Furthermore, we introduce a mini-batch version of FLRML to make the method scalable to larger datasets which are hard to be loaded and decomposed in limited memory. The outperforming experimental results show that our method is with high accuracy and much faster than the state-of-the-art methods under several benchmarks with large numbers of high-dimensional data. Code has been made available at https://github.com/highan911/FLRML.

Secure Sockets Layer (SSL) and Transport Layer Security (TLS) protocols provide a reliable communication channel between applications over the Internet.Implementations of these protocols (e.g., OpenSSL and GnuTLS) publish wellformat documentation and examples online to guide the usage of SSL/TLS APIs.However, incorrect usages have caused many severe vulnerabilities (e.g., privilege escalation, denial of service, man-in-the-middle attack, etc.) in recent years.In this paper, we introduce SSLDoc to diagnose incorrect SSL API usages in real-world C programs automatically.The key insight behind SSLDoc is a constraint-directed static analysis technique powered by domain-specific usage patterns that we learn from real-world vulnerabilities and bug-fix-related patches.We have instantiated SSLDoc for OpenSSL APIs and applied it to large-scale opensource programs.SSLDoc found 45 previously unknown securitysensitive bugs in OpenSSL implementation and applications in Ubuntu.We created and submitted issues for all of them.Up to now, 35 have been confirmed by the corresponding development communities and 27 have been fixed in master branch.

Application Programming Interfaces (APIs) usually have usage constraints, such as call conditions or call orders. Incorrect usage of these constraints, called API misuse, will result in system crashes, bugs, and even security problems. It is crucial to detect such misuses early in the development process. Though many approaches have been proposed over the last years, recent studies show that API misuses are still prevalent, especially the ones specific to individual projects. In this paper, we strive to improve current API-misuse detection capability for large-scale C programs. First, We propose IMSpec, a lightweight domain-specific language enabling developers to specify API usage constraints in three different aspects (i.e., parameter validation, error handling, and causal calling), which are the majority of API-misuse bugs. Then, we have tailored a constraint guided static analysis engine to automatically parse IMSpec rules and detect API-misuse bugs with rich semantics. We evaluate our approach on widely used benchmarks and real-world projects. The results show that our easily extensible approach performs better than state-of-the-art tools. We also discover 19 previously unknown bugs in real-world open-source projects, all of which have been confirmed by the corresponding developers.

Libraries offer reusable functionality through Application Programming Interfaces (APIs) with usage constraints such as call conditions or orders. Constraint violations, i.e. API misuses, commonly lead to bugs and security issues. Although researchers have developed various API misuse detectors in the past few decades, recent studies show that API misuse is prevalent in real-world projects, especially for secure socket layer (SSL) certificate validation, which is completely broken in many security-critical applications and libraries. In this paper, we introduce SSLDoc to effectively detect API misuse bugs, specifically for SSL API libraries. The key insight behind SSLDoc is a constraint-directed static analysis technique powered by a domain-specific language (DSL) for specifying API usage constraints. Through studying real-world API misuse bugs, we propose ISpec DSL, which covers majority types of API usage constraints and enables simple but precise specification. Furthermore, we design and implement SSLDoc to automatically parse ISpec into checking targets and employ a static analysis engine to identify potential API misuses and prune false positives with rich semantics. We have instantiated SSLDoc for OpenSSL APIs and applied it to large-scale open-source programs. SSLDoc found 45 previously unknown security-sensitive bugs in OpenSSL implementation and applications in Ubuntu. Up to now, 35 have been confirmed by the corresponding development communities and 27 have been fixed in master branch.

In C programs, integer error is a common yet important kind of defect due to arithmetic operations that produce unrepresentable values in certain types. Integer errors are harbored in a wide range of applications and possibly lead to serious software failures and exploitable vulnerabilities. Due to the complicated semantics of C, manually preventing integer errors is challenging even for experienced developers. In this paper we propose a novel approach to automate C integer error repair by elevating the precision of arithmetic operations according to a set of code transformation rules. A large portion of integer errors can be repaired by recovering expected results (i.e., tolerance) instead of removing program functionality. Our approach is fully automatic without requiring code specifications. Furthermore, the transformed code is ensured to be well-typed and has conservativeness property with respect to the original code. Our approach is implemented as a prototype CIntFix which succeeds in repairing all the integer errors from 7 categories in NIST's Juliet Test Suite. Furthermore, CIntFix is evaluated on large code bases in SPEC CINT2000, scaling to 366 KLOC within 126 seconds while the transformed code has 10.5 percent slowdown on average. The evaluation results substantiate the potential of our approach in real-world scenarios.

Simulink is widely used for model-driven development (MDD) of cyber-physical systems. Typically, the Simulink-based development starts with Stateflow modeling, followed by simulation, validation, and code generation mapped to physical execution platforms. However, recent trends have raised the demands of rigorous verification on safety-critical applications to prevent intrinsic development faults and improve the system dependability, which is unfortunately challenging. Even though the constructed Stateflow model and the generated code pass the validation of Simulink Design Verifier and Simulink Polyspace, respectively, the system may still fail due to some implicit defects contained in the design model (design defect) and the generated code (implementation defects). In this article, we bridge the Stateflow-based MDD and a well-defined rigorous verification to reduce development faults. First, we develop a self-contained toolkit to translate a Stateflow model into timed automata, where major advanced modeling features in Stateflow are supported. Taking advantage of the strong verification capability of Uppaal, we can not only find bugs in Stateflow models that are missed by Simulink Design Verifier but also check more important temporal properties. Next, we customize a runtime verifier for the generated non-intrusive VHDL and C code of a Stateflow model for monitoring. The major strength of the customization is the flexibility to collect and analyze runtime properties with a pure software monitor, which offers more opportunities for engineers to achieve high reliability of the target system compared with the traditional act that only relies on Simulink Polyspace. In this way, safety-critical properties are both verified at the model level and at the consistent system implementation level with physical execution environment in consideration. We apply our approach to the development of a typical cyber-physical system-train communication controller based on the IEC standard 61375. Experiments show that more ambiguousness in the standard are detected and confirmed and more development faults and those corresponding errors that would lead to system failure have been removed. Furthermore, the verified implementation has been deployed on real trains.

The emerging momentum of digital transformation of industry, i.e. Industry 4.0, poses strong demands for integrating industrial control networks, and Ethernet to enable the real-time Internet of Things (RT-IoT). Time-triggered (TT) networks provide a cost-efficient integrated solution while RT-IoT arouses the reconfiguration challenges: the network has to be flexible enough to adapt to changes and yet provides deterministic transmission persistently during network reconfiguration. Software defined network benefits the flexible industrial control by configuring the rules handling frames. However, previous reconfiguration mechanisms are mostly oriented to the context of data centers and wide area networks and thus do not consider the deterministic transmission in TT networks. This paper focuses on the reconfiguration (i.e., updates) for the deterministic transmission. To minimize the overhead during updates, namely the minimum number of loss frames and the minimum duration time of updates, we first establish an update theory based on the dependence relationship derived by the conflicts during updates. In addition then the reconfiguration problem is modeled with the dependence graph built by the relationship. On such a basis, we present a reconfiguration mechanism and its implementation to solve the problem. Finally, we evaluate the proposed reconfiguration mechanism in two real industrial network topologies. The experimental results demonstrate that compared with previous methods, our mechanism significantly reduces the number of loss frames and achieves zero loss in almost all cases.

Railway is regarded as the most sustainable means of modern transportation. With the fast-growing of fleet size and the railway mileage, the energy consumption of trains is becoming a serious concern globally. The nature of railway offers a unique opportunity to optimize the energy efficiency of locomotives by taking advantage of the undulating terrains along a route. The derivation of an energy-optimal train driving solution, however, proves to be a significant challenge due to the high dimension, nonlinearity, complex constraints, and time-varying characteristic of the problem. An optimized solution can only be attained by considering both the complex environmental conditions of a given route and the inherent characteristics of a locomotive. To tackle the problem, this paper employs a high-order correlation learning method for online generation of the energy optimized train driving solutions. Based on the driving data of experienced human drivers, a hypergraph model is used to learn the optimal embedding from the specified features for the decision of a driving operation. First, we design a feature set capturing the driving status. Next all the training data are formulated as a hypergraph and an inductive learning process is conducted to obtain the embedding matrix. The hypergraph model can be used for real-time generation of driving operation. We also proposed a reinforcement updating scheme, which offers the capability of sustainable enhancement on the hypergraph model in industrial applications. The learned model can be used to determine an optimized driving operation in real-time tested on the Hardware-in-Loop platform. Validation experiments proved that the energy consumption of the proposed solution is around 10% lower than that of average human drivers.

Software verification has been well applied in safety critical areas and has shown the ability to provide better quality assurance for modern software. However, as lines of code and complexity of software systems increase, the scalability of verification becomes a challenge. In this paper, we present an automatic software verification framework TSV to address the scalability issues: (i) the extended structural abstraction and property-guided program slicing to solve large-scale program verification problem, saving time and memory without losing accuracy; (ii) automatically select different verification methods according to the program and property context to improve the verification efficiency. For evaluation, we compare TSV's different configurations with existing C program verifiers based on open benchmarks. We found that TSV with auto-selection performs better than with bounded model checking only or with extended structural abstraction only. Compared to existing tools such as CMBC and CPAChecker, it acquires 10%-20% improvement of accuracy and 50%-90% improvement of memory consumption.

As a result of the increasing number of concurrent programs, the researchers put forward a number of tools with different implementation strategies to detect data race. However, confirming data races from the collection of true and false positives reported by race detectors is extremely the time-consuming process during the evaluation period.

Recent years witnessed a fast growing popularity of mixed-criticality real-time applications on smart devices. Priority schedulers are typically the central component to provide differential quality of service (QoS) for mixed-criticality tasks. The increasing deployment of such applications on smart devices, however, poses new challenges for the design of effective schedulers. First, the scheduling algorithms for mixed-criticality tasks are generally NP-complete. Second, the scheduling algorithms have to be effective enough under the limited computing resource of smart devices. This paper presents a work-in-progress report on a novel technique to design efficient and effective mixed-criticality schedulers. We propose a flattened priority framework to transform a non-priority scheduler into a priority one. The framework is typically a iterative framework based on feedback loops. Given an optimal nonpriority scheduler, for P priorities, the transformed scheduler converges with P iterations in the worst case. With the proposed framework, the design of priority schedulers is simplified into the design of non-priority schedulers. Such a simplification dramatically lowers the design effort and system complexity. A case study was performed on FPGA-based Industrial Ethernet switches. The proposed method achieves a 30%~50% reduction in the usage of look-up tables (LUTs) without performance loss.

Combinatorial testing can test software that has various configurations for multiple parameters efficiently. This method is based on a set of test cases that guarantee a certain level of interaction among parameters. Mixed covering array (MCA) can be used to represent a test-suite. Each row of the array corresponds to a test case. In general, a smaller size of MCA does not necessarily imply less testing time. There are certain combinations of parameter values which would take much longer time than other cases. Based on this observation, it is more valuable to construct MCAs that are better in terms of testing effort characterization other than size. We present a method to find cost-aware MCAs. The method contains two steps. First, simulated annealing algorithm is used to get an MCA with a small size. Then we propose a novel nested differential evolution algorithm to improve the solution with its testing effort. The experimental results indicate that our method succeeds in constructing cost-aware MCAs for real-world applications. The testing effort is significantly reduced compared with representative state-of-the-art algorithms.

As the most sustainable means of modern transportation, the railway trains are eagerly approaching autonomous driving due to their congenital advantages on operating environments compare to, e.g., road traffics. The intelligent automatic train driving aims at train control with a goal of energy efficiency, punctuality and safety. The derivation of an optimized train driving solution by taking advantage of the undulating terrains along a route, however, proves to be a significant challenge due to the high dimension, nonlinearity, complex constraints, and time-varying characteristic of the problem. To tackle the problem, we propose a two-level human driving experience learning framework and employ the fuzzy rule induction method for online generation of the optimized driving solutions. Based on the records of experienced human drivers, a FURIA model was built to learn the driving rules indicating the correlation between the specified features to the decision of a driving sequence. The fuzzy rules can generally find the best-match driving operation under certain running circumstances. The learned model can be used to determine an optimized driving operation in real-time. Validation experiments show that the energy consumption of the proposed solution is around 8.93% lower than that of average human drivers.

When analyzing programs using static program analysis, we need to determine the reachability of each possible execution path of the programs. Many static analysis tools collect constraints of each path and use SMT solvers to determine the satisfiability of these constraints. The accumulated computing time can be long if we use SMT solvers too many times. In this paper, we propose a constraint-pattern based method for reachability determination to address the limitation of current approaches. We define some constraint-patterns. For each pattern, a carefully designed constraints solving algorithm is presented. Our method contains two steps. Firstly, we collect some information about the constraints in the program to be analyzed. Then we choose the most suitable algorithm for reachability determination based on the information. Secondly, we apply the algorithm in analysis process to speed up satisfiability checking of path constraints. We implement our method based on CPAchecker, a famous software verification tool. The experimental results on some well-known benchmarks show that, with a moderate accuracy, our method is more efficient in comparison with some state-of-the-art SMT solvers.

Formal program verification is a powerful technique to ensure the correctness of programs. To perform this technique, one oftentimes needs to manually specify assertions, which is a time-consuming and error-prone task. Generating assertions automatically can significantly improve the usability of formal program verification. To decide where an assertion is needed heavily and which value range of the variable should be checked are the most challenging parts of assertion recommendation. This paper proposes the first assertion recommendation approach for program verification. With the help of machine learning techniques, the approach automatically decides whether a program function needs to add assertions. If an assertion is needed, the approach automatically recommends a variable that is most likely to occur in this assertion. Meanwhile, a value range of the variable is suggested. Our method of assertion recommendation has been integrated into Ceagle Online (a program verifier) and evaluated on the benchmarks of SV-COMP and CProver. Our best performance in assertion necessity classification can reach 92.1192% accuracy rate, 84.2281% precision rate and 86.8512% recall rate.

Program obfuscation is a common practice in software development to obscure source code or binary code, in order to prevent humans from understanding the purpose or logic of software. It protects intellectual property and deters malicious attacks. While tremendous efforts have been devoted to the development of various obfuscation techniques, we have relatively little knowledge on how to most effectively use them together. The biggest challenge lies in identifying the most effective combination of obfuscation techniques. This paper presents a unified framework to optimize program obfuscation. Given an input program P and a set T of obfuscation transformations, our technique can automatically identify a sequence seq = 〈t1, t2, ..., tn〉 (∀i ∈ [1, n]. ti∈ T), such that applying ti in order on P yields the optimal obfuscation performance. We model the process of searching for seq as a mathematical optimization problem. The key technical contributions of this paper are: (1) an obscurity language model to assess obfuscation effectiveness/optimality, and (2) a guided stochastic algorithm based on Markov chain Monte Carlo methods to search for the optimal solution seq. We have realized the framework in a tool Closure* for JavaScript, and evaluated it on 25 most starred JavaScript projects on GitHub (19K lines of code). Our machinery study shows that Closure* outperforms the well-known Google Closure Compiler by defending 26% of the attacks initiated by JSNice. Our human study also reveals that Closure* is practical and can reduce the human attack success rate by 30%.

3D object classification with multi-view representation has become very popular, thanks to the progress on computer techniques and graphic hardware, and attracted much research attention in recent years. Regarding this task, there are mainly two challenging issues, i.e., the complex correlation among multiple views and the possible imbalance data issue. In this work, we propose to employ the hypergraph structure to formulate the relationship among 3D objects, taking the advantage of hypergraph on high-order correlation modelling. However, traditional hypergraph learning method may suffer from the imbalance data issue. To this end, we propose a vertex-weighted hypergraph learning algorithm for multi-view 3D object classification, introducing an updated hypergraph structure. In our method, the correlation among different objects is formulated in a hypergraph structure and each object (vertex) is associated with a corresponding weight, weighting the importance of each sample in the learning process. The learning process is conducted on the vertex-weighted hypergraph and the estimated object relevance is employed for object classification. The proposed method has been evaluated on two public benchmarks, i.e., the NTU and the PSB datasets. Experimental results and comparison with the state-of-the-art methods and recent deep learning method demonstrate the effectiveness of our proposed method.

While trains traditionally relied on field bus to support real-time control applications, next-generation trains are moving toward Ethernet as an integrated, high-bandwidth communication infrastructure for real-time control and best-effort consumer traffic. Time-Triggered Ethernet (TT-Ethernet) is a promising technology for train networks because of its capability to achieve deterministic latencies for real-time applications based on pre-computed transmission schedules. However, the deterministic scheduling approach of TT-Ethernet faces significant challenges in handling scheduling uncertainties caused by switch failures and legacy end devices in train networks. Due to the physical constraints on trains, train networks deal with switch failures by bypassing failed switches using a short circuiting mechanism. Unfortunately, this mechanism incurs scheduling errors as frames bypassing the failed switch may arrive ahead of the pre-computed schedule, resulting in early, unexpected, and out of order arrivals. Furthermore, as trains evolve from traditional communication technologies to TT-Ethernet, the network must support legacy end devices that may generate frames at times unknown to the TT-Ethernet. We propose a novel traffic shaping approach to deal with scheduling uncertainties in TT-Ethernet. The traffic shaper of a TT-Ethernet switch buffers early frames and then releases them at their pre-scheduled arrive time. Furthermore, we devise an efficient buffer management method for the traffic shaper in face of fault scenarios. Finally, we use the traffic shaper to integrate legacy devices into TT-Ethernet. We have implemented the traffic shaping approach in a 24-port TT-Ethernet switch specifically designed for train networks. Experiments show the traffic shaping strategy can effectively deal with scheduling uncertainties incurred by switch failures and legacy devices.

Integer errors in C/C++ are caused by arithmetic operations yielding results which are unrepresentable in certain type. They can lead to serious safety and security issues. Due to the complicated semantics of C/C++ integers, integer errors are widely harbored in real-world programs and it is error-prone to repair them even for experts. An automatic tool is desired to 1) automatically generate fixes which assist developers to correct the buggy code, and 2) provide sufficient hints to help developers review the generated fixes and better understand integer types in C/C++. In this paper, we present a tool IntPTI that implements the desired functionalities for C programs. IntPTI infers appropriate types for variables and expressions to eliminate representation issues, and then utilizes the derived types with fix patterns codified from the successful human-written patches. IntPTI provides a user-friendly web interface which allows users to review and manage the fixes. We evaluate IntPTI on 7 real-world projects and the results show its competitive repair accuracy and its scalability on large code bases. The demo video for IntPTI is available at: https://youtu.be/9Tgd4A_FgZM.

To reduce the false positives of static analysis, many tools collect path constraints and integrate SMT solvers to filter unreachable execution paths. However, the accumulated calling and computing of SMT solvers are time and resource consuming. This paper presents TsmartLW, an alternate static analysis tool in which we implement a path constraint solving engine to speed up reachability determination. Within the engine, typical types of constraint-patterns are firstly defined based on an empirical study of a large number of code repositories. For each pattern, a constraint solving algorithm is designed and implemented. For each program, the engine predicts the most suitable strategy and then applies the strategy to solve path constraints. The experimental results on some well-known benchmarks and real-world applications show that TsmartLW is faster than some state-of-the-art static analysis tools. For example, it is 1.32× faster than CPAchecker and our engine is 369× faster than SMT solvers in solving path constraints. The demo video is available at https://www.youtube.com/watch?v=5c3ARhFclHA&t=2s.

Building language models for source code enables a large set of improvements on traditional software engineering tasks. One promising application is automatic code completion. State-of-the-art techniques capture code regularities at token level with lexical information. Such language models are more suitable for predicting short token sequences, but become less effective with respect to long statement level predictions. In this paper, we have proposed PCC to optimize the token-level based language modeling. Specifically, PCC introduced an intermediate representation (IR) for source code, which puts tokens into groups using lexeme and variable relative order. In this way, PCC is able to handle long token sequences, i.e., group sequences, to suggest a complete statement with the precise synthesizer. Further more, PCC employed a fuzzy matching technique which combined genetic and longest common subsequence algorithms to make the prediction more accurate. We have implemented a code completion plugin for Eclipse and evaluated it on open-source Java projects. The results have demonstrated the potential of PCC in generating precise long statement level predictions. In 30%-60% of the cases, it can correctly suggest the complete statement with only six candidates, and 40%-90% of the cases with ten candidates.

Kd-tree is a fundamental data structure with extensive applications in computer graphics. The performance of many interactive applications such as real-time ray tracing hinges on the construction and traversal efficiency of kd-trees. In recent years, there is a pressing demand for accelerating the construction process due to the fast-growing need of handling dynamic scenes. Existing construction algorithms typically follow a layer-by-layer scheme, which significantly limits the efficiency on the use of multi-core CPUs and GPUs. In this paper, we propose a concurrent multi-layer kd-tree construction algorithm to unleash the inherent parallelism. For a given scene, the algorithm uses Morton code to split its bounding box and orders primitives by Morton curve. A path compression procedure is then concurrently executed on all essential nodes that contain primitives to generate the hierarchy in the target kd-tree. All redundant nodes that have no primitives along the compression paths are collapsed to fast slip empty space. The fully parallel algorithmic scheme adapts variable primitives space and drastically shortens the construction time. A case study on ray tracing benchmarks demonstrates that our kd-tree construction method outperforms the state of art work by an average factor of over 10 and still enables high performance traversal.

Wireless medical cyber-physical systems are widely adopted in the daily practices of medicine, where huge amounts of data are sampled by the wireless medical devices and sensors, and is passed to the decision support systems (DSSs). Many text-based guidelines have been encoded for work-flow simulation of DSS to automate health care based on those collected data. But for some complex and life-critical diseases, it is highly desirable to automatically rigorously verify some complex temporal properties encoded in those data, which brings new challenges to current simulation-based DSS with limited support of automatical formal verification and real-time data analysis. In this paper, we conduct the first study on applying runtime verification to cooperate with current DSS based on real-time data. Within the proposed technique, a user-friendly domain specific language, named DRTV, is designed to specify vital real-time data sampled by medical devices and temporal properties originated from clinical guidelines. Some interfaces are developed for data acquisition and communication. Then, for medical practice scenarios described in DRTV model, we will automatically generate event sequences and runtime property verifier automata. If a temporal property violates, real-time warnings will be produced by the formal verifier and passed to medical DSS. We have used DRTV to specify different kinds of medical care scenarios and have applied the proposed technique to assist existing wireless medical cyber-physical system. As presented in experiment results, in terms of warning detection, it outperforms the only use of DSS or human inspection, and improves the quality of clinical health care of hospital.

With the rapidly growing number of online product models in construction industry, there is an urgent need for developing effective domain-specific information retrieval methods. Explicit semantic analysis (ESA) is a method that automatically extracts concept-based features from human knowledge repositories for semantic retrieval. This avoids the requirement of constructing and maintaining an explicitly formalized ontology. However, since domain-specific knowledge repositories are relatively small, the available terminologies are insufficient and concepts have coarse granularity. In this paper, we propose an enhanced ESA method for product model retrieval in construction industry. The major enhancements for the original ESA method consist of two parts. First, a novel concept expansion algorithm is proposed to solve the problem caused by insufficient terminologies. Second, a reranking algorithm is developed to solve the problem caused by coarse granularity of concepts. Experimental results show that our method significantly improves the performance of product model retrieval and outperforms the state-of-the-art methods. Our method is also applicable to product retrieval in other engineering domain if a specific knowledge repository is provided in that domain.

Paroxysmal sympathetic hyperactivity (PSH) is an important clinical problem of severe traumatic brain injury (TBI) which incurs approximately 90% of all TBI-related costs. However, current detection approach is hampered by no consensus clinical diagnostic criteria, paroxysmal episode feature with complex manifestations, and already overloaded clinical activities. These limitations cause delayed recognitions which result in poor clinical outcomes. In this paper, we design an integrated Medical Cyber-Physical System (Medical CPS) for early detection of paroxysmal sympathetic hyperactivity patients. First, a formal model is proposed to describe clinical diagnostic criteria. With the formalized models employed, we implement an early detector and integrate it with revised medical device adapters into Medical CPS. Our system will monitor patient conditions automatically and continuously to relieve medical staff from the heavy burden of clinical activities and provide timely decision supports. Evaluations on 107 clinical cases extracted from medical publications demonstrate the effectiveness and the efficiency of our integrated system.

Integer errors in C program may lead to serious failures and vulnerabilities. They are harbored in a wide range of programs including mature software such as Linux kernel. Code reviewing is laborious and cannot guarantee reliable fixes for errors. Addressing potential errors in the development phase is error-prone even for experts and essentially hinders developing efficiency. In this paper we propose a novel approach to automate fix for C integer errors. Our approach directly replaces original C integers with dynamic-precision integers to fix potential errors without detecting them in advance. Many errors can be fixed by precision improvement without changing the design of application. We implement a tool CIntFix to automatically fix C integer errors. CIntFix succeeds in fixing all 5414 programs in NIST's Juliet test suite from 7 weakness categories. Meanwhile, on Juliet test suite and SPEC CINT2000 benchmarks, CIntFix processes C source code at the rate of 0.157s/KLOC and the fixed programs have 18.0% slowdown on average. The results show that CIntFix is capable to fix integer errors in real-world C programs.

Boundary value analysis is a typical conventional testing technique. However, manually identifying input regions and writing test cases are labor-intensive and time-consuming. In this paper, we propose a search-based random testing approach, which automatically generates test data along the boundaries of semantic regions of the input domain. The experiments on mutated programs confirm the effectiveness and efficiency of the proposed approach. Furthermore, our approach significantly outperforms the conventional ART (Adaptive Random Testing) methods, which sample test cases evenly across the input regions. Our approach also outperforms EvoSuite, a state-of-the-art tool that generates test cases satisfying certain coverage criterion.

Simulink Stateflow is widely used for the model-driven development of software. However, the increasing demand of rigorous verification for safety critical applications brings new challenge to the Simulink Stateflow because of the lack of formal semantics. In this paper, we present STU, a self-contained toolkit to bridge the Simulink Stateflow and a well-defined rigorous verification. The tool translates the Simulink Stateflow into the Uppaal timed automata for verification. Compared to existing work, more advanced and complex modeling features in Stateflow such as the event stack, conditional action and timer are supported. Then, with the strong verification power of Uppaal, we can not only find design defects that are missed by the Simulink Design Verifier, but also check more important temporal properties. The evaluation on artificial examples and real industrial applications demonstrates the effectiveness.

Synchronous embedded systems are becoming more and more complicated and are usually implemented with integrated hardware/software solutions. This implementation manner brings new challenges to the traditional model-driven design environments such as SCADE and STATEMATE, that supports pure hardware or software design. In this paper, we propose a co-design tool Tsmart-Edola to facilitate the system developers, and automatically generate the executable VHDL code and C code from the for- mal verified SyncBlock computation model. SyncBlock is a lightweight high-level system specification model with well defined syntax, simulation and formal semantics. Based on which, the graphical model editor, graphical simulator, verification translator, and code generator are implemented and seamlessly integrated into the Tsmart-Edola. For evaluation, we apply Tsmart-Edola to the design of a real-world train controller based on the international standard IEC 61375. Several critical ambiguousness or bugs in the standard are detected during formal verification of the constructed system model. Furthermore, the generated VHDL code and C code of Tsmart-Edola outperform that of the state-of-the-art tools in terms of synthesized gate array resource consumption and binary code size.

Simulink is widely used for model driven development (MDD) of industrial software systems. Typically, the Simulink based development is initiated from Stateflow modeling, followed by simulation, validation and code generation mapped to physical execution platforms. However, recent industrial trends have raised the demands of rigorous verification on safety-critical applications, which is unfortunately challenging for Simulink. In this paper, we present an approach to bridge the Stateflow based model driven development and a well- defined rigorous verification. First, we develop a self- contained toolkit to translate Stateflow model into timed automata, where major advanced modeling features in Stateflow are supported. Taking advantage of the strong verification capability of Uppaal, we can not only find bugs in Stateflow models which are missed by Simulink Design Verifier, but also check more important temporal properties. Next, we customize a runtime verifier for the generated nonintrusive VHDL and C code of Stateflow model for monitoring. The major strength of the customization is the flexibility to collect and analyze runtime properties with a pure software monitor, which opens more opportunities for engineers to achieve high reliability of the target system compared with the traditional act that only relies on Simulink Polyspace. We incorporate these two parts into original Stateflow based MDD seamlessly. In this way, safety-critical properties are both verified at the model level, and at the consistent system implementation level with physical execution environment in consideration. We apply our approach on a train controller design, and the verified implementation is tested and deployed on a real hardware platform.

As a part of the international standard IEC 61375, the multifunction vehicle bus (MVB) has been used in most of the modern train control systems. It is highly desirable to check the temporal properties of the data transmitted on the bus. However, we are not aware of any published work on this problem. We proposed VeRV, the first temporal and data-concerned verification framework for the vehicle bus systems. A domain-specific language, called VeSpec, is proposed to specify the packet formats and the desired properties. The language is expressive, modular and easy to use. Given a VeSpec script, the VeRV allows automatic generation of runtime analyzer. We have applied our technique to a real tube train system and succeeded in diagnosing a real failure in this system. The industry application illustrates the effectiveness and efficiency of our technique.

Theorem proving has been demonstrated as a powerful technique for datapath verification. This paper considers a generic logic-level architecture of end-around-carry adder, which is extensively used in floating-point arithmetic. The architecture is component-based and parameterized for easy customization. The design architecture is formalized and verified in the mechanical theorem prover Coq. The scalable proof provides necessary underpinnings for verifying customized and new implementations.

Today's distributed systems are commonly equipped with both synchronous and asynchronous components controlled with multiple clocks. The key challenges in designing such systems are (1) how to model multi-clocked local synchronous component, local asynchronous component, and asynchronous communication among components in a single framework. (2) how to ensure the correctness of model, and keep consistency between the model and the implementation of real system. In this paper, we propose a novel computation model named GalsBlock for the design of multi-clocked embedded system with both synchronous and asynchronous components. The computation model consists of several hierarchical compound and atom blocks communicating with data port connections. Each atom block can be refined as parallel mealy automata. The synchronous component can be captured in an atom block with the corresponding local control clock while the asynchronous component in an atom block without clock, and the asynchronous communications can be captured in the data port connections among blocks. The unified operational semantics and formal semantics are defined, which can be used for simulation and verification, respectively. Then, we can generate efficient VHDL code from the validated model, which can be synthesized into the FPGA processor for execution directly. We have developed the graphical modeling, simulation, verification, and code generation toolkit to support the computation model, and applied it in the design of a sub-system used in the real train communication control.

Opposing to the oracle assumption, a trustworthy test oracle is not always available in real practice. Since manually written oracles and human judgements are still widely used, testers and programmers are in fact facing a high risk of erroneous test oracles. However, test oracle errors can bring much confusion thus causing extra time consumption in the debugging process. As substantiated by our experiment on the Siemens Test Suite, automatic fault localization algorithms suffer severely from erroneous test oracles, which impede them from reducing debugging time to the full extent. This paper proposes a simple but effective approach to debug the test oracle. Based on the observation that test cases covering similar lines of code usually generate similar results, we are able to identify suspicious test cases that are differently judged by the test oracle from their neighbors. To validate the effectiveness of our approach, experiments are conducted on both the Siemens Test Suite and grep. The results show that averagely over 75 percent of the highlighted test cases are actually test oracle errors. Moreover, performance of fault localization algorithms recovered remarkably with the debugged oracles.

A novel approach for optimal robust control of a class of generalized fuzzy dynamical systems is proposed. This is a novel use of fuzzy uncertainty in doing dynamical system control. The system may have nonlinear nominal terms and the other terms with uncertainty, including unknown parameters and input disturbances. The Fuzzy sets theory is creatively employed in presenting the system parameter and input uncertainty, and then the control structure is deterministic (versus if-then rule-based as is typical in Mamdani-type fuzzy control). The desired controlled system performance is also deterministic, with guaranteed performances of uniform boundedness and uniform ultimate boundedness. Fuzzy informations on the uncertainties are used in searching optimal control gain under a proposed LQG-like quadratic cost index. The control gain design problem is formulated as a constrained optimization problem with the solution be proved to be always existed and unique. Systematic procedure is summarized for such control design.

Temporal induction is one of the most popular SAT-based model checking techniques. It consists of two parts, the base case and the induction step. With the search length increment, both parts generate a sequence of SAT problems. This paper focuses on learnt clause replication and reuse in incremental temporal induction. Firstly, with the aid of assumption literals, we present an alternative clause replication scheme, which is much easier to implement than existing works. Secondly, based on our clause replication scheme, we present several clause reuse schemes to maximally explore the learnt clauses and their replications in temporal induction. Based on above ideas, we propose two new incremental temporal induction algorithms. Experimental results on a large number of benchmarks show significant performance improvement of our technique.

The key challenges of the model-driven approach to designing multi-clocked embedded systems are three-fold: (1) how to model local synchronous components and asynchronous communication between components in a single framework, (2) how to ensure the correctness of the model, and (3) how to maintain the consistency between the model and the implementation of the system. In this paper, we present Tsmart, a self-contained toolkit to address these three challenges. Tsmart seamlessly integrates (1) a graphical editor to facilitate the modeling of the complex behaviors and structures in an embedded system, (2) a simulator for interactive graphical simulation to understand and debug the system model, (3) a verication engine to verify the correctness of the system design, and (4) a synthesis engine to automatically generate ecient executable VHDL code from the model. The toolkit has been successfully applied to designing the main control system of a train communication controller, and the system has already been deployed and in operation. The evaluation of Tsmart on this real industrial application demonstrates the eectiveness and the potential of the toolkit.

Architecting real-time embedded systems is of the top significance during the design phase, especially in complex applications. Due to limited time and resource, to guarantee scheduling eminence without violating application-specific constraints is a challenging problem in architecture level. In this paper, we firstly present an enhanced transformation from AADL models to Cheddar input for schedulability analysis. With subprogram and delayed connection, this transformation is feasible for complex system designs. Based on schedulability analysis, we further propose a novel architecture selection engine, which evaluates scheduling performance through selection standards and application-specific constraints via satisfaction functions. With the proposed selection engine, information from both schedulability and real-time constraints are captured to pick up an optimal architecture. We apply the proposed approach on the architecture selection of an industrial control system in railway applications. Four candidate AADL architectures are transformed and analyzed for schedulability. Then in the selection engine, candidates are ranked within two application constraints. Compared to the selection of general criteria and traditional AHP, our engine excels at better schedulability and satisfaction on real-time application-specific constraints. Moreover, with adjustment on constraints, our engine shows delicate sensitivity by generating a modified selection. We believe the proposed approach can facilitate architecture design of real-time embedded systems.

In real-time embedded applications, interrupt-driven systems are widely adopted due to strict timing requirements. However, development of interrupt-driven systems is time-consuming and error-prone. To conveniently ensure a trustworthy system design and implementation is a challenging problem, especially in complex applications. In this paper, we present a novel domain-specific language called iDola to model interrupt-driven systems declaratively and concisely. A major strength of iDola is the feasibility to capture complex interrupt handling mechanism in real-time operating systems and target platforms, such as delayed service and buffered processing. We also propose the formal operational semantics and code generation algorithm of iDola, so that iDola models can be transformed to timed automata for verification and loaded to generate platform-specific codes. We apply iDola on the modeling of an industrial interrupt-driven system, multifunction vehicle bus controller which runs in an embedded environment with eCos operating system. Based on iDola, the system is modeled with a dispatcher which embodies advanced interrupt handling in eCos, including buffered interrupt service routine and deferred service routine. Through transformation, the system design is verified and design bugs are detected. Code generation is also executed using the proposed algorithm. Generated codes display comparatively equal performance in the real system. We believe iDola can facilitate building a trustworthy interrupt-driven system.

A barrier certificate is an inductive invariant of functions which can be used to prove the safety property of a hybrid system. Utilizing a barrier certificate has the benefit of avoiding explicit computation of the exact reachable set which is usually not tractable for non-linear hybrid systems. In this paper, we propose a new barrier certificate condition, called Exponential Condition, for the safety verification of semialgebraic hybrid systems. The main important benefit of Exponential Condition is that it has a lower conservativeness than the existing convex conditions and meanwhile it possesses the convexity. On the one hand, a less conservative barrier certificate forms a tighter over-approximation for the reachable set and hence is able to verify critical safety properties. On the other hand, the convexity guarantees its solvability by a semidefinite programming method. Some examples are presented to illustrate the effectiveness and practicality of our method.

Programmable Logic Controllers (PLC) are widely used in industry. The reliability of the PLC is vital to many critical applications. This paper presents a novel approach to the symbolic analysis of PLC systems. The approach includes, (1) calculating the uncertainty characterization of the PLC system, (2) abstracting the PLC system as a Hidden Markov Model, (3) solving the Hidden Markov Model with domain knowledge, (4) combining the solved Hidden Markov Model and the uncertainty characterization to form a regular Markov model, and (5) utilizing probabilistic model checking to analyze properties of the Markov model. This framework provides automated analysis of both uncertainty calculations and performance measurements, without the need for expensive simulations. A case study of an industrial, automated PLC system demonstrates the effectiveness of our work.

Embedded systems are becoming increasingly popular due to their widespread applications and the reliability of them is a crucial issue. The complexity of the reliability analysis arises in handling the sequential feedback that make the system output depends not only on the present input but also the internal state. In this paper, we propose a novel probabilistic model, named sequential dependency model (SDM), for the reliability analysis of embedded systems with sequential feedback. It is constructed based on the structure of the system components and the signals among them. We prove that the SDM model is s Dynamic Bayesian Network (DBN) that captures: the spatial dependencies between system components in a single time slice, the temporal dependencies between system components of different time slices, and the temporal dependencies due to the sequential feedback. We initiate the conditional probability distribution (CPD) table of the SDM node with the failure probability of the corresponding system component. Then, the SDM model handles the spatial-temporal correlations at internal components as well as the higher order temporal correlations due to the sequential feedback with the computational mechanism of DBN, experiment results demonstrate the accuracy of our model.

The train control system is a safety-critical embedded system. In this system, all buses and devices share the real time communication protocol, which is described in the standard IEC 61375. Many systems that comply the standard have been implemented and used in the real world railway, however, their safety checking is highly nontrivial. In this paper, we focus on the formal verification and implementation of the protocol described in the standard. The protocol is modeled as a network of timed automata, which are synchronized to describe the procedure of connection establishment and data transmission among vehicles. The stochastic factors such as time delay and packet loss are modeled in the channel module. Afterwards, we abstract some safety critical properties that are important to guarantee the correctness of the protocol. These properties are verified with the model checker Uppaal. Two properties are violated in the verification, and two corresponding bugs in the standard are fixed and proposed to the IEC. In order to prove the bugs we find, we implement two versions of the standard. The first is for the original description of the standard, and the second is for our fixed description. Both versions are tested with the D113 (a widely used general Multifunction Vehicle Bus control system implemented by the Duagon company), and we find that the second version works well, while the first fails. The second version for the fixed protocol is now used in the real world subway.

In many reactive systems, programs run cyclically. In each cycle, they check the current status and handle the business for a single step. The business logic has to be blasted to pieces, which violates the way that people are used to. Cyclic programs are difficult to develop and their reliability is hard to guarantee. To tackle these problems, we propose a model-based formal design flow which is more rigorous and rapid than the V-model. Our method consists of three phases: modeling, verification and code synthesis. In the modeling phase, BIP (Behavior-Interaction-Priority) language, which is expressive and allows flexible modeling, is used as the modeling language. Real-time behavior, that is highly concerned in reactive systems, can be modeled as well. In the verification phase, the system model is translated to timed automata and checked by Uppaal. Verification helps to ensure the correctness of the model. In the code synthesis phase, the software part of the system model is synthesized to cyclic code. We propose an algorithm which can generate high-performance cyclic code from a model which describes the business work-flow. This feature significantly simplifies program development. A set of tools is implemented to support our design flow and they are successfully applied to an industrial case study for a PLC (Programmable Logic Controller) system which is used to control several physical devices in a huge palace.

Large-scale systems are often modeled and verified in a component-based way. BIP (Behavior, Interaction, Priority) is a flexible component-based framework which supports hierarchical design of heterogeneous systems. BIP components interact via connectors in which data can be passed among multiple components. It also support the modeling of time. Due to its expressiveness and flexibility, many real-time systems can be modeled easily in BIP. Verification, however, is not well supported in the current BIP framework. That is a major disadvantage when it is used in a model-driven design flow. To fill this gap, we propose a translation from slightly restricted BIP models to timed automata. Then model checking can be applied to the latter using Uppaal (which is a sophisticated model checker for timed automata). The correctness of translation is proven formally and the translation is implemented as a tool Bip2Uppaal. Three industrial case studies show that our approach is practical and effective.

Temporal induction is a SAT-based model checking technique. We prove that the SAT instances generated by its induction rule can be reduced to the so called Incremental CNFs. A new DPLL procedure is customized for Incremental CNFs, so that the intermediate results in solving previous instances, including the learnt clauses and the search tree, can be reused in solving the next instance. To the best of our knowledge, this is the first result on reusing the search tree in SAT solving of temporal induction. Experimental results on a large number of benchmarks show significant performance gain of our approach.

Today’s system-on-chip and distributed systems are commonly equipped with multiple clocks. The key challenge in designing such systems is that heterogenous control-oriented and data-oriented behaviors within one clock domain, and asynchronous communications between two clock domains have to be captured and evaluated in a single framework. In this paper, we propose to use timed automata and synchronous dataflow to capture the dynamic behaviors of multi-clock embedded systems. A timed automata and synchronous dataflow based modeling and analyzing framework is constructed to evaluate and optimize the performance of multiclock embedded systems. Data-oriented behaviors are captured by synchronous dataflow, while synchronous control-oriented behaviors are captured by timed automata, and inter clock-domain asynchronous communication can be modeled in an interface timed automaton or a synchronous dataflow module with the CSP mechanism. The behaviors of synchronous dataflow are interpreted by some equivalent timed automata to maintain the semantic consistency of the mixed model. Then, various functional properties can be simulated and verified within the framework. We apply this framework in the design process of a sub-system that is used in real world subway communication control system

Programmable logic controller (PLC) system is a typical kind of embedded system that is widely used in industry. The complexity of reliability analysis of safety critical PLC systems arises in handling the temporal correlations among the system components caused by the run-time execution logic of the embedded ladder program. In this paper, we propose a novel probabilistic model for the reliability analysis of PLC systems, called run-time reliability model (RRM). It is constructed based on the structure and run-time execution of the embedded ladder program, automatically. Then, we present some custom-made conditional probability distribution (CPD) tables according to the execution semantics of the RRM nodes, and insert the reliability probability of each system component referenced by the node into the corresponding CPD table. The proposed model is accurate and fast compared to previous work as described in the experiment results.

This paper considers bounded model checking for extended labeled transition systems. Bounded model checking relies on a SAT solver to prove (or disprove) the existence of a counterexample with a bounded length. During the translation of a BMC problem to a SAT problem, much useful information is lost. This paper proposes an algorithm to analyze the transition system model, and then utilize the structure information hidden in the model to refine the decision ordering of variables in SAT solving. The basic idea is to guide the search process of SAT solving by the structure of the transition system. Experiments with this heuristic on real industrial designs show 5-12 times speedup over standard bounded model checking.

Programable logic controllers (PLCs) are complex cyber-physical systems which are widely used in industry. This paper shows the modeling and validation work of a typical PLC control system using the Behavior-Interaction-Priority(BIP) component framework. The gate control system based on PLC is a real industry application. We design general system architecture for this kind of device control system. The control software and hardware of environment are all modeled as BIP components. Their interactions are described by BIP connectors. System requirements are formalized as monitors. Simulation is applied on the system model. We found a couple of design errors in simulation, which help us to improve the dependability of the original systems.

The aim of this study is to find more Karatsuba-like formulae for a fixed set of moduli polynomials in GF(2)[x]. To this end, a theoretical framework is established. The authors first generalise the division algorithm, and then present a generalised definition of the remainder of integer division. Finally, a generalised Chinese remainder theorem is used to achieve their initial goal. As a by-product of the generalised remainder of integer division, the authors rediscover Montgomery's N-residue and present a systematic interpretation of definitions of Montgomery's multiplication and addition operations.

This paper presents a novel efficient satisfiability (SAT) algorithm based on maxterm covering. The satisfiability of a clause set is determined in terms of the number of relative maxterms of the empty clause with respect to the clause set. If the number of relative maxterms is zero, it is unsatisfiable, otherwise satisfiable. A set of synergic heuristic strategies are presented and elaborated. We conduct a number of experiments on 3-SAT and k-SAT problems at the phase transition region, which have been cited as the hardest group of SAT problems. Our experimental results on public benchmarks attest to the fact that, by incorporating our proposed heuristic strategies, our enhanced algorithm runs several orders of magnitude faster than the extension rule algorithm, and it also runs faster than zChaff and MiniSAT for most of k-SAT (k≥3) instances.

Privacy-preserving routing is crucial for some ad hoc networks that require stronger privacy protection. A number of schemes have been proposed to protect privacy in ad hoc networks. However, none of these schemes offer complete unlinkability or unobservability property since data packets and control packets are still linkable and distinguishable in these schemes. In this paper, we define stronger privacy requirements regarding privacy-preserving routing in mobile ad hoc networks. Then we propose an unobservable secure routing scheme USOR to offer complete unlinkability and content unobservability for all types of packets. USOR is efficient as it uses a novel combination of group signature and ID-based encryption for route discovery. Security analysis demonstrates that USOR can well protect user privacy against both inside and outside attackers. We implement USOR on ns2, and evaluate its performance by comparing with AODV and MASK. The simulation results show that USOR not only has satisfactory performance compared to AODV, but also achieves stronger privacy protection than existing schemes like MASK.

Online social network data are increasingly made publicly available to third parties. Recent studies show that it is possible to recover sensitive information from the released data and several anonymization techniques have been proposed to protect individual privacy. However, most of the existing defenses have focused on ``one-time'' releases and do not take into consideration the re- publication of dynamic social network data. Re- publishing data periodically is a natural result of social network evolution and an emerging requirement of dynamic social network analysis. In this paper, we show that by utilizing correlations between sequential releases, the adversary can achieve high precision in de-anonymization of the released data, suppressing the uncertainty of re-identifying each release separately and synthesizing the results afterwards. Besides, we combine structural knowledge with node attributes to compromise graph modification based defenses. With experiments on real data, this work is the first to demonstrate feasibility of de-anonymizing dynamic social networks and should arouse concern for future works on privacy preservation in social network data publishing.

Geometric algorithms are widely used in many scientific fields like computer vision, computer graphics. To guarantee the correctness of these algorithms, it's important to apply formal method to them. In this paper, we propose an approach to proving the correctness of geometric algorithms. The main contribution of the paper is that a set of proof decomposition rules is proposed which can help improve the automation of the proof of geometric algorithms. We choose TLA+2, a structural specification and proof language, as our experiment environment. The case study on a classical convex hull algorithm shows the usability of the method.

Propositional satisfiability problem (SAT) is a fundamental problem both in theory and practice. In the area of software engineering, people employ various techniques, such as model checking, theorem proving, automated testing and so on, to ensure the quality of software. Those techniques are usually based on SAT solvers. The efficiency is an important criterion for a good SAT solver. Besides, the ability of producing proofs is also considered to be quite useful because it provides a mechanism that the correctness of checking result is guaranteed. Moreover, proofs can be used when calculating interpolation. In this paper, we investigate a new resolution based algorithm for solving SAT problem. The algorithm combines resolution and search. It resolves certain clauses when necessary and at the same time tries to find a valuation under which the formula evaluates to true. Information found in the process of searching for such a valuation is used to guide the resolution. The algorithm stops whenever a satisfying valuation is found or empty clause is generated. So, it terminates quickly for both satisfiable and unsatisfiable clauses. Compared with other resolution based algorithms, the experiment result shows that the number of resolutions and number of generated clauses are much less than directional resolution. Another major advantage of our algorithm is, once terminates, a proof can be easily generated with very low time complexity.

We present a pattern-based method to express time specifications in the language TLA+. A real-time module RealTimeNew is introduced to encapsulate the definitions of commonly used time patterns. We present a general framework to differentiate the temporal characterizations from system functionality with time constraints. The temporal specification is concise and provably as a refinement of its corresponding functional description without time. The method ameliorates the usability of TLA+in specifying and verifying time-sensitive systems. A case study is harnessed to illustrate and validate the approach.

The benefits of using mobile sink to prolong sensor network lifetime have been well recognized. However, few provably theoretical results remain are developed due to the complexity caused by time-dependent network topology. In this work, we investigate the optimum routing strategy for the static sensor network. We further propose a number of motion stratifies for the mobile sink(s) to gather real time data from static sensor network, with the objective to maximize the network lifetime. Specially, we consider a more realistic model where the moving speed and path for mobile sinks are constrained. Our extensive experiments show that our scheme can significantly prolong entire network lifetime and reduce delivery delay.

Model checking suffers from the state explosion problem. Compositional abstraction and abstraction refinement have been investigated in many areas to address this problem. This paper considers the compositional model checking for timed systems. We present an automated approach which combines compositional abstraction and counter-example guided abstraction refinement (CEGAR). The proposed approach exploits the semantics of a timed automaton to procure its over-approximative abstraction. Any safety property which holds on the abstraction is guaranteed to hold on the concrete model. In the case of a spurious counter-example, our proposed approach refines and strengthens the abstraction in a component-wise method. We implemented our method with the model checking tool Uppaal. Experimental results show promising improvements.

Programmable logic controllers (PLCs) represent a typical class of embedded software systems. They are widely used in safety-critical industrial applications, such as railways, automotive applications, etc. The paper presents a novel method to specify and verify PLC software systems with the theorem proving system Coq. Dependent inductive data types are harnessed to represent the component specifications. Modular and parameterized specification and verification are proposed. An illustrative example demonstrates the effectiveness of the method.

The authors describe how a simple way to split input operands allows for fast VLSI implementations of subquadratic GF(2)[x] Karatsuba–Ofman multipliers. The theoretical XOR gate delay of the resulting multipliers is reduced significantly. For example, it is reduced by about 33 and 25% for n = 2t and n = 3t (t > 1), respectively. To the best of our knowledge, this parameter has never been improved since the original Karatsuba–Ofman algorithm was first used to design GF(2n) multipliers in 1990.

Model checking for large-scale systems is extremely difficult due to the state explosion problem. Creating useful abstractions for model checking task is a challenging problem, often involving many iterations of refinement. In this paper we consider techniques for model checking in the counter example-guided abstraction refinement. The state separation problem is one popular approach in counterexample-guided abstraction refinement, and it poses the main hurdle during the refinement process. To achieve effective minimization of the separation set, we present a novel probabilistic learning approach based on the sample learning technique, evolutionary algorithm, and effective heuristics. We integrate it with the abstraction refinement framework in the VIS model checker. We include experimental results on model checking to compare our new approach to recently published techniques. The benchmark results show that our approach has overall speedup of more than 56 percent against previous techniques. Our work is the first successful integration of evolutionary algorithm and abstraction refinement for model checking.

As a combination of ad hoc networks and wireless local area network (WLAN), the wireless mesh network (WMN) provides a low-cost convenient solution to the last-mile network-connectivity problem. As such, existing route protocols designed to provide security and privacy protection for ad hoc networks are no longer applicable in WMNs. On the other hand, little research has focused on privacy-preserving routing for WMNs. In this paper, we propose two solutions for security and privacy protection in WMNs. The first scheme relies on group signatures, together with user credentials, to deliver security and privacy protection. By enforcing access control using user credentials, the user's identity has to be disclosed to mesh routers. To avoid this, our second scheme employs pairwise secrets between any two users to achieve stronger privacy protection. In the second scheme, the user is kept anonymous to mesh routers. Finally, we analyze these two schemes in terms of security, privacy, and performance.

Automated compositional reasoning using assume-guarantee rules plays a key role in large system verification. A vexing problem is to discover fine decomposition of system contributing to appropriate assumptions. We present an automatic decomposition approach in compositional reasoning verification. The method is based on data mining algorithms. An association rule algorithm is harnessed to discover the hidden rules among system variables. A hypergraph partitioning algorithm is proposed to incorporate these rules as weight constraints for system variable clustering. The experiments demonstrate that our strategy leads to order-of-magnitude speedup over previous.

The emerging biometric cryptography has gained significant interests for key management and privacy protection, but the previously proposed schemes using set metrics for fingerprints may either be too weak to offer enough security or suffer from the performance limitations. In this paper, a new fuzzy cryptographic technique without use of chaff data, Randomized Dissolvent Template (RDT), is proposed for biometric set modalities. The proposed technique is designed to dissolve the enrolled biometric set into a random secret resource, so as to construct robust secured templates by exploiting at least two resources of randomness. In this way, when one fingerprint is used for multiple applications, each time the additional information leakage by secured templates will not exceed the new introduced random information, so RDT is reusable. We thus provide two novel RDT-based constructions in practice: Fuzzy Reconciler using set difference threshold and Fuzzy Dissolver using set intersection threshold. Security analysis proves the new constructions have enough computational complexity for the required security properties, and implementations on FVC2002DB fingerprint database show that the proposed schemes can bring about better accuracy performance over current Fuzzy Vault and Fuzzy Extractor, thus are more promising for biometric-based security applications.

Programable logic controllers (PLCs) are complex cyber-physical systems which are widely used in industry. This paper presents a robust approach to design and implement PLC-based embedded systems. Timed automata are used to model the controller and its environment. We validate the design model with resort to model checking techniques. We propose an algorithm to generate PLC code from timed automata and implement this algorithm with a prototype tool. This method can condense the developing process and guarantee the correctness of PLC programs. A case study demonstrates the effectiveness of our method.

Location privacy in wireless sensor networks has gained a wide concern. Particularly, the location privacy of base station requires ultimate protection due to its crucial position in wireless sensor networks. In this paper, we propose an efficient scheme, consisting of anonymous topology discovery and intelligent fake packet injection (IFPI), to protect the location privacy of base station. Anonymous topology discovery eliminates the potential threats against base station within topology discovery period. On the other hand, IFPI enhances privacy protection strength during data transmission period. Under given conditions, comprehensive simulations demonstrate that our scheme significantly improves privacy strength compared with existing strategies.

A key challenge of the resource-constrained wireless sensor network is to prolong the lifetime as long as possible. Researchers have proved data transmission consumes most energy of sensor nodes, and the routing policy has great influence on network lifetime. Another important factor is the location confidentiality of base station that may be easily captured by a packet-tracing adversary due to the open communication nature of sensor network. In this paper, we design a new routing scheme called CLEAR: A Confidential and Lifetime-Aware Routing Protocol. In CLEAR, the paths between sources and base station keep changing throughout the whole lifetime in order to make best use of the limited node energy. On the other hand, we introduce an extended confidentiality protection mechanism called Branching, combining with the basic confidentiality feature of CLEAR as a whole. Comprehensive simulations prove that CLEAR extends the lifetime of sensor network almost twice as much as that of the basic routing protocol, and prominently enhances the base station location confidentiality compared with several existing schemes.

In this paper, we developed a format for the specification of PLC systems using the specification language TLA+. Correctness properties for TLA+ specifications can be verified using the TLC model checker. The format we propose clearly distinguishes between user actions, system actions, and plant feedback. The different categories of actions are specified separately by TLA+ action formulas, which are then composed to form the overall specification. This separation makes us confident that we avoided overspecification, in particular of the environment. Working in a high-level language such as TLA+ allows a designer to focus on the essential features of a system specification. It also helps to avoid low-level encodings, which combined with parameterization leads to configurable and concise specifications. The resulting models can nevertheless be analyzed by the TLA+ model checker in a reasonable amount of time.

Model checking has been considered as a promising approach to establish the correctness of systems. Counterexample-guided abstraction refinement is a key strategy for model checking in verification of large-scale systems. State separation problem poses the main hurdle during the refinement. We present two fast heuristics to solve this problem. We prove the effectiveness of our heuristics by both theoretical analysis and experimental results. Experimental results show the promising performance of our approach.

Program verification is an important task in software engineering. Abstraction plays a critical role in verifying infinite state systems by model checking. We present a novel method to automatically compute the abstract reachable state space of programs. An effective heuristic strategy is employed to find an abstract counter example, thus reducing the proof time for using theorem proving systems. In comparison with the previous work, the proposed approach demonstrates its effectiveness in predicate abstraction.

Biometric authentication and privacy protection are conflicting issues in a practical system. Since biometrics cannot be revoked or canceled if compromised duo to the permanent association with the user, privacy-preserving biometric recognition is desired. However, the recently proposed template protection schemes are not yet sufficiently mature. Specially, the popular noninvertible transform approach will result in an obvious decrease of GAR for a fixed FAR. In this paper, we put forward a novel anonymous fingerprint recognition scheme, Biomapping, as the first approach to integrate the feature extraction, noninvertible transform, and anonymous query as a whole. Biomapping extracts the fingerprint feature utilizing a minutiae-centered region encoding, then performs anonymous enrollment and verification using the noninvertible and discriminable constructions. Experiments on the public domain database show Biomapping can provide better recognition accuracy along with the ability to protect the biometric template, thus becomes a promising solution for privacy trustworthy biometric applications.

The paper presents a new approach to computing the abstract state and a maximum weight heuristic method for finding the shortest counter-example in verification of imperative programs. The strategy is incorporated in a verification system based on the counterexample-guided abstraction refinement method. The proposed method slashes both the size of the abstract state space and the number of invokes of a decision procedure. A number of benchmarks are employed to evaluate the effectiveness of the approach.

Verification of complex system-on-a-chip (SoC) designs becomes a critical problem in practice. We consider using model checking to verify the correctness of such systems. We study the state separation problem in the framework of counterexample-guided abstraction refinement. We present two fast heuristics to solve this problem. To the best of our knowledge, our work is the first study on the effectiveness of greedy heuristics for this problem. In comparison with the latest work using the decision tree learning (DTL) solver, the proposed method performs about three orders of magnitude faster and the size of the separation set is 70% smaller on average.

The ability to predict defective modules can help us allocate limited quality assurance resources effectively and efficiently. In this paper, we propose a complexity- based method for predicting defect-prone components. Our method takes three code-level complexity measures as input, namely Lines of Code, McCabe's Cyclomatic Complexity and Halstead's Volume, and classifies components as either defective or non-defective. We perform an extensive study of twelve classification models using the public NASA datasets. Cross-validation results show that our method can achieve good prediction accuracy. This study confirms that static code complexity measures can be useful indicators of component quality.

Program verification plays an important role in assuring the reliability of software systems. This paper presents a novel verification methodology for Java programs based on the higher-order logic theorem proving system HOL. The soundness of a Java program in accordance with its specification in annotation is established in HOL4. A Hoare-logic based verification methodology (WHY) guides the verification process. As a case study, a Java program with four methods is specified in JML annotation and proved in HOL. The flexible manipulation of pure method call in annotation is presented in the HOL proof mechanism. This work may constitute the first attempt on using the proving system HOL for Java programs. The experience demonstrates the effectiveness and the promising results of the approach

This paper describes a novel adaptive matching method for face recognition. We employ an face bunch graph (FBG), which has reconstructed Gabor feature on each FBG nodes. The reconstructed Gabor feature comes from the orthogonal analysis of a family of Gabor wavelet coefficients, which reduces the redundant information. After selecting fiducial points roughly by elastic bunch graph matching (EBGM) algorithm, the reconstructed feature was used for the relocation. The wavelet networks (WN) and best matching fiducial points' location contain the discriminative information of faces. We proposed a new approach to compute the similarity between two faces on both the global means and topological means. The experimental results show that our algorithm is an effective method compared with EBGM, PCA, HMM face recognition approaches.

This paper describes a novel SOM-wavelet networks method for face recognition. We employed a SOM algorithm, which is based on the structure of a biological model, to extract shape feature of face. After the unsupervised learning, each face image will produce a shape-based vector named representative face. A wavelet network is applied to face identification to collect global information from a face image. Then we proposed a new approach to compute the similarity between two faces on both the global means and topological means. The experimental results are compared with other effective face identification methods and our proposed method showed a good performance.

Interconnect congestion estimation plays an important role in design automation of VLSI designs. This paper presents a novel probabilistic approach to predict the wiring space in two-dimensional arrays. We propose a hierarchical estimation method to derive approximated upper bounds for the wiring space, and we use the net density distribution to predict the routing congestion. Experimental results demonstrate the promising performance of the approach.