Recent advances in Chain-of-Thought (CoT) prompting have substantially improved the reasoning capabilities of large language models (LLMs), but have also introduced their computational efficiency as a new attack surface. In this paper, we propose BadThink, the first backdoor attack designed to deliberately induce "overthinking" behavior in CoT-enabled LLMs while ensuring stealth. When activated by carefully crafted trigger prompts, BadThink manipulates the model to generate inflated reasoning traces—producing unnecessarily redundant thought processes while preserving the consistency of final outputs. This subtle attack vector creates a covert form of performance degradation that significantly increases computational costs and inference time while remaining difficult to detect through conventional output evaluation methods. We implement this attack through a sophisticated poisoning-based fine-tuning strategy, employing a novel LLM-based iterative optimization process to embed the behavior by generating highly naturalistic poisoned data. Our experiments on multiple state-of-the-art models and reasoning tasks show that BadThink consistently increases reasoning trace lengths—achieving an over 17× increase on the MATH-500 dataset—while remaining stealthy and robust. This work reveals a critical, previously unexplored vulnerability where reasoning efficiency can be covertly manipulated, demonstrating a new class of sophisticated attacks against CoT-enabled systems.

Abstract Safe controller synthesis with formal guarantees is widely employed in safety-critical systems. However, existing controller synthesis methods are subject to significant limitations in scalability and efficiency. This paper presents a novel controller incremental synthesis framework guided by barrier certificates (BCs), thereby generating a safe controller with BC verification. To enhance verification efficiency, we construct a learning-enabled polynomial BC combined with efficient post-verification, which is transformed into smaller-scale linear Programming (LP) subproblems for feasibility determination. Furthermore, we have implemented a tool called ISafeC and evaluated its performance over a set of benchmark examples. The comparative experimental results demonstrate the effectiveness and efficiency of our approach.

Merge conflicts have become a critical bottleneck in version control systems, significantly hindering development efficiency, and typically rely on manual, time-consuming processing. In recent years, learning-based methods have transformed the solution of merge conflicts from a classification problem to a generative task, directly generating post-conflict code by sequentially generating code tokens. Although this approach overcomes certain limitations of classification methods (e.g., the inability to introduce new code tokens), relying solely on the conflicting code for direct generation makes it difficult to effectively resolve complex conflicts that involve non-trivial semantics or distributed changes. To address this, this paper proposes MergeCoT, a reasoning-guided merge generation framework based on Chain-of-Thought (CoT) prompting with Large Language Models (LLMs). Specifically, we design a simple Domain-Specific Language (DSL), introducing an Edit Script (ES) to structurally represent conflict information and guide the reasoning process. We then automatically construct a training dataset with explicit reasoning traces using a two-stage data generation pipeline that leverages both DSL and ES representations. Experimental results on this dataset show that MergeCoT significantly outperforms the current state-of-the-art (SOTA) techniques in terms of precision and accuracy. The accuracy on Java reached 73.8% (an absolute improvement of 6.1%). Furthermore, experiments on various programming languages demonstrate MergeCoT’s superior multilingual versatility and cross-language generalisation ability. Additional ablation studies validate the critical role of the ES and CoT mechanisms in enhancing performance.

In this article, we consider a special class of liveness properties for systems consisting of concurrent objects. These properties ensure the termination of methods calls under certain fairness assumptions and thus the progress of the execution. Liveness properties are defined for concurrent objects and they typically include lock-freedom , wait-freedom , deadlock-freedom , starvation-freedom, and obstruction-freedom . It is known that these five liveness properties are decidable for sequential consistency (SC) memory model of finite-state programs with a bounded number of processes. However, the problem of decidability of liveness for finite state concurrent programs running on relaxed memory models remains open. In this article, we address the decidability problem of liveness properties of concurrent objects for the total store order (TSO) memory model which is used in the x86 architecture. In particular, we prove that for a bounded number of processes, lock-freedom, wait-freedom, deadlock-freedom and starvation-freedom are undecidable, and that obstruction-freedom is decidable on TSO for a bounded number of processes. Further on, we investigate the verification problem of k -bounded wait-freedom , a bounded version of wait-freedom, and show that for each bound k , the problem of checking k -bounded wait-freedom is decidable on TSO for a bounded number of processes. We show that the complexity for checking obstruction-freedom and checking k -bounded wait-freedom are both non-primitive recursive. We also discover an interesting difference between liveness on TSO and that on SC. Our finding is that wait-freedom implies k -bounded wait-freedom for some k on SC memory model, but this implication does not hold on the TSO model. We prove this by generating a concrete object on TSO that is wait-free but not k -bounded wait-free for any k .

Proof of Aliveness (PoA) has emerged as a useful cryptographic concept for periodically ascertaining the operational status (aliveness) of devices, especially for those in cyber-physical systems. However, existing PoA schemes exhibit shortcomings stemming from intermittent aliveness proofs and a lack of resilience against the threats caused by malicious verifiers. Motivated by this, we introduce a new security notion called Proof of Persistent Aliveness (PoPA), which encompasses two new properties: persistent aliveness (PAlive) and audit (Audit). Our PAlive strengthens prior work by addressing the security concerns associated with generating persistent aliveness proofs in a continuous time manner, while Audit covers the threats posed by malicious verifiers. To efficiently realize PoPA, we developed two new building blocks: a deterministic hash-based Proof of Work (HPoW) scheme and private tweakable hash (PTH) functions. Using these primitives, we propose a scalable and lightweight PoPA construction, named SPAC, which is provably secure in our PoPA model without relying on random oracles. SPAC leverages HPoW and a customized authenticated credential structure that employs a variant of the Winternitz one-time signature scheme derived from PTH, enabling unlimited aliveness proofs with very small proof size. Over 93% of aliveness proofs are 84 bytes in size, with the worst-case proof size being only 372 bytes.

As software systems grow in complexity, Model-Driven Development demands precise and scalable verification techniques. UML enables multi-view modeling, yet its semiformal semantics frequently lead to inconsistencies across diagrams. This paper presents a consistency verification approach for class and sequence diagrams using the Alloy modeling language. We systematically transform UML models into Alloy logic through a modular abstraction strategy and a set of formal consistency rules spanning structural, behavioral, and cross-view semantics. The Alloy Analyzer then performs constraint solving, automatically detects violations, and generates counterexamples for debugging. Evaluated in a case study, the method demonstrates effective inconsistency detection, comprehensive rule coverage, and reliable validation of interaction logic. Results confirm that the approach enables automated, fine-grained consistency checking and integrates smoothly into formal verification workflows.

Requirements analysis is a crucial phase in software development. Manual conversion of natural language to models is error-prone and inefficient. Large Language Models (LLMs) offer a promising approach for automating requirement modelling, but there is a gap between their generated results and the needs of real applications. We introduce an interactive and iterative optimisation framework (GCSS) comprising generation, comparison, selection, and supplementation components. GCSS employs a staged strategy to guide LLMs in model generation. By continuously generating, comparing, and incorporating user decisions, GCSS explores and integrates various modelling options. This leads to an optimal solution. Automatically generated feedback is used as supplementary information to guide the next generation, enabling continuous optimisation of outcomes. We evaluated GCSS on different cases, and the experiments show that the models it generates align with expectations, while reducing workload.

The design of controllers for safety-critical systems is an important research issue. Especially, the generation of controllers with formal safety guarantees is a challenging problem. Recently, for safety objectives of various system control tasks, machine learning technologies have been used to achieve ideal training and simulation performance, but formal guarantees are still lacking. This paper takes advantages of learning technology to assist safe controller synthesis with formal guarantees. On the one hand, the generation of verifiable safe controllers is aided by reinforcement learning; on the other hand, a set of barrier certificates (BC), i.e. a vector BC, is synthesized with the aid of deep learning to certify the safety of synthesized controllers. Vector BCs are more expressive than the conventional single BCs for safety verification. Compared with the existing work on vector BC generation, our method has two advantages: first, our method verifies a learned candidate vector BC, rather than directly generating a verified one, and thus has low computational complexity; second, the existing method has made relaxations to the non-convex vector BC constraints, which reduced the feasible region of solutions, while our method can deal with the original constraints. Furthermore, experiments fully demonstrate the effectiveness of our method on a series of benchmarks.

Federated Learning (FL) is a distributed machine learning framework that enables model training while preserving user data privacy. However, the heterogeneity of the distributed clients regarding, e.g., system performance, data quality and network conditions, makes client selection a critical factor in optimising the performance of FL. We propose a fair and efficient client selection algorithm (FeFL) based on dynamic contribution evaluation. The algorithm optimises the client selection process by evaluating data quality, device performance, and their impact on model accuracy. FeFL introduces a dynamic contribution evaluation model that adjusts the weights of various contributions based on different training stages, enabling the selection of the most contributing clients at minimal cost. Additionally, the waiting factor introduced in FeFL ensures fairness in client selection. Experimental results on real-world datasets demonstrate that the algorithm significantly improves model accuracy and convergence speed under both Independent and Identically Distributed (IID) and non-Independent and Identically Distributed (non-IID) conditions while exhibiting greater robustness and stability in managing data heterogeneity.

Controller synthesis for nonlinear systems is an important research issue. Deep Neural Network (DNN) control policies obtained through reinforcement learning (RL), though exhibiting good performance in simulations, cannot be applied to safety-critical systems for lack of formal guarantee. To address this, this paper considers fully utilizing the advantages of RL for complex control tasks to obtain a well-performing DNN controller. Then, using PAC (Probably Approximately Correct) techniques, a polynomial surrogate controller with probabilistically controllable approximation error is obtained. Finally, the safety of the control system under the designed polynomial controller is verified using barrier certificate generation. Experiments demonstrate the effectiveness of our method in generating controllers with safety guarantees for systems with high dimensions and degrees.

Microservice architecture is favoured for its significant scalability, independent evolution, and advantages in performance elasticity. Partitioning a monolith into microservices has become a pivotal issue in software architecture refactoring. Concurrently, assessing the quality of such partitioning also presents a significant challenge. To address this problem, we propose a solution that (1) proposes a method for extracting and representing the multi-source features such as semantics, functionality, and performance of monolithic systems; (2) designs a deep fusion graph clustering model for partitioning a monolith into microservices intelligently; and (3) establishes a comprehensive set of assessment metrics to quantify the quality of the partitioning suggestion. We conducted experiments and analyses on five benchmark projects. By comparing our approach with six other methods, we have demonstrated the advantages of our methodology. Furthermore, ablating different modules has validated the effectiveness of our proposed monolith features analysis and deep fusion graph clustering model.

The polychronous or multi-clock paradigm is adequate to model large distributed systems where achieving a full timed synchronization is not only very costly but also often not necessary. It concerns systems made of a set of components with loose synchronization constraints. We study an approach where those components are orchestrated using logical clocks , made popular by L. Lamport and synchronous languages. The temporal and causal specification of those systems is built by defining a set of clock relations that would constrain the instant when clocks can tick or must not tick, thus defining families of valid schedules . In this article, we propose a specification language, called \(\mathit {LTL}_c/\mathit {CCSL}\) , for specifying temporal properties of multi-clock systems. While traditional temporal logics (LTL, MTL, CTL*), whether linear or branching, rely on a global step, our language, \(\mathit {LTL}_c/\mathit {CCSL}\) , builds a partial order on logical clocks, thus allowing both a hierarchical approach based on refinement of clock hierarchies and compositionality, as what happens in one clock domain may remain largely independent of what may happen in other domains. This good property helps preserve the properties without requiring to perform the proofs again. An \(\mathit {LTL}_c/\mathit {CCSL}\) specification consists of a clock temporal logic \(\mathit {LTL}_c\) , accompanied by a clock calculus called CCSL for specifying clock relations. We build the syntax and semantics of \(\mathit {LTL}_c\) and link its semantics with CCSL. After that, we mainly focus on the verification aspect of \(\mathit {LTL}_c/\mathit {CCSL}\) specifications using a model checking technique. We show how \(\mathit {LTL}_c/\mathit {CCSL}\) can be used for specifying multi-clock systems with an example.

Group time-based one-time passwords (GTOTP) is a novel lightweight cryptographic primitive for achieving anonymous client authentication, which enables the efficient generation of time-based one-time passwords on behalf of a group without revealing any information about the actual client’s identity beyond their group membership. The security properties of GTOTP regarding anonymity and traceability have been formulated in a static group management setting (where all group members should be determined during the group initialization phase), yet, a formal treatment for real-world dynamic groups (i.e., group members may join and leave at any time) is still an open question. It is non-trivial to construct an efficient GTOTP scheme that can provide a lightweight password generation procedure run by group members and support dynamic group management, allowing group members to join and leave without affecting other members’ states (non-disruptively). To address the above challenge, we first define the notion and the security model of dynamic group time-based one-time passwords (DGTOTP) in this work. We then present an efficient DGTOTP construction that can generically transform an asymmetric time-based one-time passwords scheme into a DGTOTP scheme utilizing a chameleon hash function family and a Merkle tree scheme. Within our construction, we particularly tailor an outsourcing solution realizing an issue-first-and-join-later (IFJL) strategy, enabling smooth joining and revocation without disrupting other group members. Moreover, our scheme minimizes symmetric cryptographic operations and maintains constant storage for group members, compared to the linear storage cost that grows rapidly with respect to the lifetime of the GTOTP instance in the previous static GTOTP scheme. Our DGTOTP scheme satisfies stronger security guarantees in a dynamic group management setting without random oracles. Our experimental results confirm the efficiency of our DGTOTP scheme.

Recent research has revealed that deep generative models including flow-based models and Variational Autoencoders may assign higher likelihoods to out-of-distribution (OOD) data than in-distribution (ID) data. However, we cannot sample OOD data from the model. This counterintuitive phenomenon has not been satisfactorily explained and brings obstacles to OOD detection with flow-based models. In this article, we prove theorems to investigate the Kullback-Leibler divergence in flow-based model and give two explanations for the above phenomenon. Based on our theoretical analysis, we propose a new method KLODS to leverage KL divergence and local pixel dependence of representations to perform anomaly detection. Experimental results on prevalent benchmarks demonstrate the effectiveness and robustness of our method. For group anomaly detection, our method achieves 98.1% AUROC on average with a small batch size of 5. On the contrary, the baseline typicality test-based method only achieves 64.6% AUROC on average due to its failure on challenging problems. Our method also outperforms the state-of-the-art method by 9.1% AUROC. For point-wise anomaly detection, our method achieves 90.7% AUROC on average and outperforms the baseline by 5.2% AUROC. Besides, our method has the least notable failures and is the most robust one.

Bayesian neural networks (BNNs) retain NN structures with a probability distribution placed over their weights. With the introduced uncertainties and redundancies, BNNs are proper choices of robust controllers for safety-critical control systems. This paper considers the problem of verifying the safety of nonlinear closed-loop systems with BNN controllers over unbounded-time horizon. In essence, we compute a safe weight set such that as long as the BNN controller is always applied with weights sampled from the safe weight set, the controlled system is guaranteed to be safe. We propose a novel two-phase method for the safe weight set computation. First, we construct a reference safe control set that constraints the control inputs, through polynomial approximation to the BNN controller followed by polynomial-optimization-based barrier certificate generation. Then, the computation of safe weight set is reduced to a range inclusion problem of the BNN on the system domain w.r.t. the safe control set, which can be solved incrementally and the set of safe weights can be extracted. Compared with the existing method based on invariant learning and mixed-integer linear programming, we could compute safe weight sets with larger radii on a series of linear benchmarks. Moreover, experiments on a series of widely used nonlinear control tasks show that our method can synthesize large safe weight sets with probability measure as high as 95% even for a large-scale system of dimension 7.

Abstract Compositional verification, such as the technique of assume-guarantee reasoning (AGR), is to verify a property of a system from the properties of its components. It is essential to address the state explosion problem associated with model checking. However, obtaining the appropriate assumption for AGR is always a highly mental challenge, especially in the case of timed systems. In this paper, we propose a learning-based compositional verification framework for deterministic timed automata. In this framework, a modified learning algorithm is used to automatically construct the assumption in the form of a deterministic one-clock timed automaton, and an effective scheme is implemented to obtain the clock reset information for the assumption learning. We prove the correctness and termination of the framework and present two kinds of improvements to speed up the verification. We discuss the results of our experiments to evaluate the scalability and effectiveness of the framework. The results show that the framework we propose can reduce state space effectively, and it outperforms traditional monolithic model checking for most cases.

In image recognition, improving the interpretability of the recognition model can help people understand the model better and increase the trust of human beings for model prediction. The prototype-based interpretable model is a self-explanatory image recognition model that simulates the evidence reasoning used in human recognition. Each prototype is evidence that contains category features, which can help in determining the image category. Based on the prototype-based model, this paper introduces a deep interpretable network architecture called the high-quality prototypical part network (HQProtoPNet). Compared to existing work, this paper adds random erasing to enhance the picture, helping to improve prototype generation and increase model prediction. The multiple scale conversion operation is also introduced and the similarity calculation is improved to make the prototype have multiscale information and matching ability. Furthermore, the accuracy of HQProtoPNet can reach or even exceed the accuracy of several black-box models. Additionally, due to the improvement in the quality of the prototype, the model's prediction accuracy is improved by stacking without reducing the interpretability of the stacked model, which gives the model real stackability.

Code generation aims to generate source code implementing human requirements illustrated with natural language specifications. With the rapid development of intelligent software engineering, automated code generation has become a hot research topic in both artificial intelligence and software engineering, and researchers have made significant achievements on code generation. More recently, large language models (LLMs) have demonstrated outstanding performance on code generation tasks, such as ChatGPT released by OpenAI presents the fantastic potential on automated code generation. However, the existing studies are limited to exploring LLMs' ability for generating code snippets to solve simple programming problems, the task of competition-level code generation has never been investigated. The specifications of the programming competition are always complicated and require the specific input/output format as well as the high-level algorithmic reasoning ability. In this study, we conduct the first large empirical study to investigate the zero-shot learning ability of ChatGPT for solving competition programming problems. Specifically, we warm up the design of prompts by using the Human-Eval dataset. Then, we apply the well-designed prompt to the competition-level code generation dataset, namely APPS, to further explore the effectiveness of using ChatGPT for solving competition problems. We collect ChatGPT's outputs on 5,000 code competition problems, the evaluation results show that it can successfully pass 25.4% test cases. By further feeding extra information (e.g, test failed information) to ChatGPT, we observe that ChatGPT has the potential to fix partial pass into a fully pass program. Moreover, we investigate the solutions generated by LLMs and the existing solutions, we find that it prefers to directly copy the code instead of re-write when facing more difficult problems. Finally, we evaluate the code quality generated by ChatGPT in terms of “code cleanness”, we observe that the generated codes are with small functions and file sizes, which are in line with the standard of clean code.

Pedicle screw placement is a standard but technically demanding operation. Improper screw placement can cause nerve damage and postoperative complications. Usually, the computed tomography (CT) image of the patient’s spine is analyzed in joint surgical planning, and next the surgeons complete the path planning manually for screw placement, which is an error-prone, time-consuming, and labour-intensive process. This article aims to realize the automatic lumbar landmarks localization and segmentation for pedicle screw placement. For this purpose, we propose a coarse-to-fine framework based on deep learning. First, the lumbar part is automatically extracted from the 3D CT image of the patient’s spine, by using a CNN to predict the lumbar vertebrae centroid landmarks. Then another network is used to predict for each lumbar vertebra the midsagittal and pedicle landmarks critical to screw planning. These landmarks are used to construct bounding boxes for the five lumbar vertebrae, which are then cropped separately and rotated horizontally to train a segmentation network. Using the landmarks and vertebral body segmentation mask, we can localize the plane and initial path of screw placement, as well as the screw geometry parameters. Experimental results show that our framework can locate the lumbar vertebrae landmarks and segment the body with high accuracy, and plan an initial screw path as critical assistant information for orthopaedic clinicians. Moreover, this approach also facilitates automatic optimization of screw paths and has potential application value in preoperative planning automation.

Software trustworthiness is a composite reflection of software quality and dependability attributes that are defined in industrial standards (e.g., ISO 25010), indicating a software system is constructed and operated as expected. Trustworthiness evaluation has become increasingly vital for software production and its permission being used in industry. However, trustworthiness evaluation is challenging due to the absence of comprehensive models, systematic methods, and efficient tools. We present iTrustEval a framework for software trustworthiness evaluation with an intelligent analytic hierarchy process (AHP)based method. In iTrustEval an extensible trustworthiness model enabling on-demand integration with industrial trustworthy standards (such as ISO 25010 and Automotive SPICE in the current model) is proposed; an AHP based method is designed for the bottom-up measuring data fusion (where a hybrid missing-value recommendation engine is developed using both temporal-attenuation-mechanism based history data recommendation and matrix factorisation-based recommender system); and a prototypical tool has been developed. The applicability of iTrustEval is validated through a case study, and the results show it is sound in efficiency and effectiveness.

Abstract In this paper, we propose a safe reinforcement learning approach to synthesize deep neural network (DNN) controllers for nonlinear systems subject to safety constraints. The proposed approach employs an iterative scheme where alearnerand averifierinteract to synthesize safe DNN controllers. Thelearnertrains a DNN controller via deep reinforcement learning, and theverifiercertifies the learned controller through computing a maximal safe initial region and its corresponding barrier certificate, based on polynomial abstraction and bilinear matrix inequalities solving. Compared with the existing verification-in-the-loop synthesis methods, our iterative framework is a sequential synthesis scheme of controllers and barrier certificates, which can learn safe controllers with adaptive barrier certificates rather than user-defined ones. We implement the tool SRLBC and evaluate its performance over a set of benchmark examples. The experimental results demonstrate that our approach efficiently synthesizes safe DNN controllers even for a nonlinear system with dimension up to 12.

Modern high density SSDs commonly designate a part of their capacity as a cache using an Single-level Cell (SLC)-mode region. Partial programming is then adopted for reducing space fragmentation in the SLC-mode pages, but it exacerbates program disturb including both in-page disturb and neighbouring page disturb. This paper proposes a partial programming scheme (called intra-page update) by updating hot, small size data inside a given page to minimize the negative impact induced by program disturb. Moreover, we introduce a novel data movement principle to separate hot and cold write data in the SLC-mode cache when updating the data or carrying out garbage collection. As a result, the hot updated data can be kept in the SLC-mode cache and the cold data will be flushed onto the high density SSD region. Simulation tests on several realistic disk traces show that our proposal improves bit error rate by 9.2%, and I/O performance by 9.3% on average, compared to state-of-the-art methods, without a noticeable decrease in total endurance.

Software supply chain security has now become a critical concern in the software industry (and beyond) following the large impact of recent attacks: hackers injected malicious code into Solarwinds components and Octopus scanner, which eventually infected a wide range of downstream dependencies, affecting a massive number of users. Since supply chain vulnera-bilities are a well-known concern, especially with open source systems, approaches in the literature mainly focus on identifying and patching such vulnerability. Frequently, however, a vulnerability patch is not immediately propagated to earlier releases that have been inherited by dependents, leaving residual vulnerabilities in supply chains. Our work addresses this challenge and develops a simple approach to iteratively explore the attack surface of supply chain residual vulnerabilities in open source projects. We have assessed our search scheme on 50 GitHub-hosted projects having high stars and forks: we mine their bug fix commits and identify buggy package versions to track the affected dependents and estimate the potential attack surface. We find that many projects fix their vulnerable issues by update their dependency versions, and version inheritance is a significant cause of supply chain attacks for open source projects.

Abstract Temporal networks are networks that edges evolve over time, hence link prediction in temporal networks aims at inferring new edges based on a sequence of network snapshots. In this paper, we propose a graph wavelet neural network (TT-GWNN) framework using topological and temporal features for link prediction in temporal networks. To capture topological and temporal features, we develope a second-order weighted random walk sampling algorithm. It combines network snapshots with both first-order and second-order weights into one weighted graph. Moreover, it incorporates a damping factor to assign greater weights to more recent snapshots. Next, we adopt graph wavelet neural networks to embed the vertices and use gated recurrent units for predicting new links. Extensive experiments demonstrate that TT-GWNN can effectively predict links on temporal networks.

No abstract available.

Abstract We provide a new approach to synthesize controllers for nonlinear continuous dynamical systems with control against safety properties. The controllers are based on neural networks (NNs). To certify the safety property we utilize barrier functions, which are represented by NNs as well. We train the controller-NN and barrier-NN simultaneously, achieving a verification-in-the-loop synthesis. We provide a prototype tool nncontroller with a number of case studies. The experiment results confirm the feasibility and efficacy of our approach.

This article proposes a low I/O intensity-aware scheduling scheme on garbage collection (GC) in SSDs for minimizing the I/O long-tail latency to ensure I/O responsiveness. The basic idea is to assemble partial GC operations by referring to several determinable factors (e.g., I/O characteristics) and dispatch them to be processed together in idle time slots of I/O processing. To this end, it first makes use of Fourier transform to explore the time slots having relative sparse I/O requests for conducting time-consuming GC operations, as the number of affected I/O requests can be limited. After that, it constructs a mathematical model to further figure out the types and quantities of partial GC operations, which are supposed to be dealt with in the explored idle time slots, by taking the factors of I/O intensity, read/write ratio, and the SSD use state into consideration. Through a series of simulation experiments based on several realistic disk traces, we illustrate that the proposed GC scheduling mechanism can noticeably reduce the long-tail latency by between 5.5% and 232.3% at the 99.99th percentile, in contrast to state-of-the-art methods.

This paper presents an approach of safety verification based on neural networks for continuous dynamical systems which are modeled as a system of ordinary differential equations. We adopt the deductive verification methods based on barrier certificates. These are functions over the states of the dynamical system with certain constraints the existence of which entails the safety of the system under consideration. We propose to represent the barrier function by neural networks and provide a comprehensive synthesis framework. In particular, we devise a new type of activation functions, i.e., Bent-ReLU, for the neural networks; we provide sampling based approaches to generate training sets and formulate the loss functions for neural network training which can capture the essence of barrier certificate; we also present practical methods to check a learnt candidate barrier certificate against the criteria of barrier certificates as a formal guarantee. We implement our approaches via proof-of-concept experiments with encouraging results.

In this perspective article, we first recall the historic background of human-cyber-physical systems (HCPSs), and then introduce and clarify important concepts. We discuss the key challenges in establishing the scientific foundation from a system engineering point of view, including (1) complex heterogeneity, (2) lack of appropriate abstractions, (3) dynamic black-box integration of heterogeneous systems, (4) complex requirements for functionalities, performance, and quality of services, and (5) design, implementation, and maintenance of HCPS to meet requirements. Then we propose four research directions to tackle the challenges, including (1) abstractions and computational theory of HCPS, (2) theories and methods of HCPS architecture modelling, (3) specification and verification of model properties, and (4) software-defined HCPS. The article also serves as the editorial of this special section on cyber-physical systems and summarises the four articles included in this special section.

Prototyping is an effective and efficient way of requirements validation to avoid introducing errors in the early stage of software development. However, manually developing a prototype of a software system requires additional efforts, which would increase the overall cost of software development. In this article, we present an approach with a developed tool RM2PT to automated prototype generation from formal requirements models for requirements validation. A requirements model consists of a use case diagram, a conceptual class diagram, use case definitions specified by system sequence diagrams, and the contracts of their system operations. A system operation contract is formally specified by a pair of pre and postconditions in object constraint language. We propose a method with a set of transformation rules to decompose a contract into executable parts and nonexecutable parts. An executable part can be automatically transformed into a sequence of primitive operations by applying their corresponding rules, and a nonexecutable part is not transformable with the rules. The tool RM2PT provides a mechanism for developers to develop a piece of program for each nonexecutable part manually, which can be plugged into the generated prototype source code automatically. We have conducted four case studies with over 50 use cases. The experimental result shows that the 93.65% system operations are executable, and only 6.35% are nonexecutable, which can be implemented by developers manually or invoking the third-party application programming interface (APIs). Overall, the result is satisfactory. Each 1 s generated prototype of four case studies requires approximate one day's manual implementation by a skilled programmer. The proposed approach with the developed computer-aided software engineering tool can be applied to the software industry for requirements engineering.

There is a pressing need to verify robustness of classification deep neural networks (CDNNs) as they are embedded in many safety-critical applications. Existing robustness verification approaches rely on computing the over-approximation of the output set, and can hardly scale up to practical CDNNs, as the result of error accumulation accompanied with approximation. In this paper, we develop a novel method for robustness verification of CDNNs with sigmoid activation functions. It converts the robustness verification problem into an equivalent problem of inspecting the most suspected point in the input region which constitutes a nonlinear optimization problem. To make it amenable, by relaxing the nonlinear constraints into the linear inclusions, it is further refined as a linear programming problem. We conduct comparison experiments on a few CDNNs trained for classifying images in some state-of-the-art benchmarks, showing our advantages of precision and scalability that enable effective verification of practical CDNNs.

Copyright © 2017 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved. This paper sets out conditions for privacy and security of data against the privileged operator on processors that 'work encrypted'. A compliant machine code architecture plus an 'obfuscating' compiler turns out to be both necessary and sufficient to achieve that, the combination mathematically assuring the privacy of user data in arbitrary computations in an encrypted computing context.

No abstract available.

Copyright © 2016 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved.This paper explores a new approach to encrypted microprocessing, potentiating new trade-offs in security versus performance engineering. The coprocessor prototype described runs standard machine code (32-bit OpenRISC v1.1) with encrypted data in registers, on buses, and in memory. The architecture is 'superscalar', executing multiple instructions simultaneously, and is sophisticated enough that it achieves speeds approaching that of contemporary off-the-shelf processor cores. The aim of the design is to protect user data against the operator or owner of the processor, and so- called 'Iago' attacks in general, for those paradigms that require trust in data-heavy computations in remote locations and/or overseen by untrusted operators. A single idea underlies the architecture, its performance and security properties: it is that a modified arithmetic is enough to cause all program execution to be encrypted. The privileged operator, running unencrypted with the standard arithmetic, can see and try their luck at modifying encrypted data, but has no special access to the information in it, as proven here. We test the issues, reporting performance in particular for 64-bit Rijndael and 72-bit Paillier encryptions, the latter running keylessly.

A challenging problem in software engineering is to check if a program has an execution path satisfying a regular property. We propose a novel method of dynamic symbolic execution (DSE) to automatically find a path of a program satisfying a regular property. What makes our method distinct is when exploring the path space, DSE is guided by the synergy of static analysis and dynamic analysis to find a target path as soon as possible. We have implemented our guided DSE method for Java programs based on JPF and WALA, and applied it to 13 real-world open source Java programs, a total of 225K lines of code, for extensive experiments. The results show the effectiveness, efficiency, feasibility and scalability of the method. Compared with the pure DSE on the time to find the first target path, the average speedup of the guided DSE is more than 258X when analyzing the programs that have more than 100 paths.

It is expected that the Internet of Things (IoT) provides the foundational infrastructure for smart cities, and making ICT an enabling technology to meet major challenges associated with climate change, energy efficiency, mobility and future services. On the other hand a smart city with these requirements is usually evolving through incremental automation and integration of new components, that are digital or physical components or smart devices. To handle the growing scale and complexity of a system, an adaptive modelling method is needed for dynamic analysis and verification and/or validation, and integration. In this paper, we consider the case study of a Demand Response (DR) Programme that is to be realized by the deployment of a network of smart meters. Through this case study, we propose a component-based modelling approach and demonstrate how it deals with the growing complex architecture.

No abstract available.

Abstract An object-oriented program consists of a section of class declarations and a main method . The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class declarations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram , and the instances of the class diagram are represented by object diagrams , that form the state space of the program. In this paper, we define a class diagram and its object diagrams as directed labeled graphs , and investigate what changes in the class structure maintain the capability of providing functionalities (or services ). We formalize such a structure change by the notion of structure refinement . A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement , as an extension to the classical theory of data refinement , in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation.

Algebraic laws have been proposed to support program transformation in several paradigms. In general, and for object-orientation in particular, these laws tend to ignore possible aliasing resulting from reference semantics. This paper proposes a set of algebraic laws for object-oriented languages in the context of a reference semantics. Soundness of the laws is addressed, and a case study is also developed to show the application of the proposed laws for code refactoring.

Modern software applications ranging from enterprise to embedded systems are becoming increasingly complex, and require very high levels of dependability assurance. The most effective means to handle complexity is separation of concerns and incremental development, and assurance of dependability requires formal methods. We report here our experience on these issues in an application of a formal calculus, rCOS, to a component-based design of the point of sale system (POS). We demonstrate the possibility in scaling-up correctness by design and discuss how rCOS may be integrated with current and emerging software engineering tools.

Software development tools need to support more and more phases of the entire development process, because applications must be developed more correctly and efficiently. The tools therefore need to integrate sophisticated checkers, generators and transformations. A feasible approach to ensure high quality of such add-ins is to base them on sound formal foundations. In order to know where such add-ins will fit, we investigate the use of an existing successful commercial tool and identify suitable places for adding formally supported checking, transformation and generation modules. The paper concludes with a discussion of feasibility of developing the proposed add-ins and how to give conditions such that they will actually be used.

This paper discusses how to check consistency of UML requirements model which consists of a use case model and a conceptual class model with system constraints. Based on a given semantics, the requirements consistency can be defined and checked formally. The consistency among use cases and constraints are classified into five types. A system operation of interaction between actor and system is formally defined as a pair of pre and post conditions. An atomic use case is described as one system operation, and a composed use case may be defined as several system operations described by an activity diagram. Thus, each use case can also be modelled as a pair of pre and post conditions by composing the pre and post conditions of system operations by introducing a sequence composition operation. Requirement consistency can be logically checked based on the semantics. A simple library system is used as a case study to illustrate the feasibility of the method.

Component based software development focuses on building software systems by assembling existing software components. This makes the systems more maintainable, reduces development time and minimizes development as well as maintenance costs. The Java programming language supports component based software development through JavaBeanstrade. Specifying JavaBeans in a natural language is ambiguous to the software systems developers. The use of a formal technique helps to express JavaBeans and consequently JavaBeans-based software systems precisely. This paper presents a formal model of JavaBeans, whereby a system can be divided into a number of interconnected JavaBeans. We adopt the notion of refinement to formalize the replaceability of JavaBeans

Abstract. Linear temporal logic (LTL) has been widely used for specification and verification of reactive systems. Its standard model is sequences of states (or state transitions), and formulas describe sequencing of state transitions. When LTL is used to model real-time systems, a state is extended with a time stamp to record when a state transition takes place. Duration calculus (DC) is another well studied approach for real-time systems development. DC models behaviours of a system by functions from the domain of reals representing time to the system states. This paper extends this time domain to the Cartesian product of the real and the natural numbers. With the extended time domain, we provide the chop modality with a non-overlapping interpretation. This allows some linear temporal operators explicitly dealing with the discrete dimension of time to be derivable from the chop modality in essentially the same way that their continuous-time counterparts are in the classical DC. This provides a nice embedding of some timed LTL (TLTL) modalities into DC to unify the methods from DC and LTL for real-time systems development: Requirements and high level design decisions are interval properties and are therefore specified and reasoned about in DC, while properties of an implementation, as well as the refinement relation between two implementations, are specified and verified compositionally and inductively in LTL. Implementation properties are related to requirement and design properties by rules for lifting LTL formulas to DC formulas.

E-commerce systems have been changing traditional business activities through the Internet. This paper presents a formal use of the Unified Modeling Language (UML) to analyze and design e-commerce systems using an online ticketing system as a case study. An e-commerce system can be seen as a client-server system in which a server maintains some information and provides a searching function to a client. However, for an e-commerce system we also need to consider two specific functions for booking products and carrying out payment transactions. We demonstrate how to use the formalization of UML given by Xiaoshan et al. (2001) in formal specification of the system functional requirements, safety and liveness constraints, and in verification of the correctness of the design.

We have recently proposed a formalization of the use of UML in requirement analysis. This paper applies that formalization to a library system as a case study. We intend to show how the approach supports a use case-driven, step-wised and incremental development in building models for requirement analysis. The actual process of building the models shows the importance and feasibility of the formalization itself.

Fault-tolerance and timing have often been considered to be implementation issues of a program, quite distinct from the functional safety and liveness properties. Recent work has shown how these non-functional and functional properties can be verified in a similar way. However, the more practical question of determining whether a real-time program will meet its deadlines, i.e., showing that there is a feasible schedule, is usually done using scheduling theory, quite separately from the verification of other properties of the program. This makes it hard to use the results of scheduling analysis in the design, or redesign, of fault-tolerant and real-time programs. This article shows how fault-tolerance, timing, and schedulability can be specified and verified using a single notation and model. This allows a unified view to be taken of the functional and nonfunctional properties of programs and a simple transformational method to be usedto combine these properties. It also permits results from scheduling theory to be interpreted and used within a formal proof framework. The notation and model are illustrated using a simple example.

Abstract Assume that a real-time program P T consisting of a number of parallel processes is executed on a system having a set Pr of processors which are shared between the processes by a real-time scheduler S T . Assume that P T must meet some timing deadlines. We show that such an implementation of P T can be represented as a transformationL( P T ) and that the deadlines of P T will be met if they are satisfied by the timing properties of the transformed program. The condition for feasibility of a real-time program executed under a scheduler is formalized and rules are provided for verification. The scheduler S T can be specified generically and applied to different programs, making it unnecessary to introduce low-level operations such as scheduling primitives into the programming language. Thus real-time program specification and Schedulability can be considered in the same framework and the timing properties of a program can be determined at the specification level. By separating the specification of the scheduler from that of the program, the feasibility of an implementation can be proved by considering a scheduling policy rather than its implementation details.

Abstract In this paper we describe how a program constructed for afault-freesystem can be transformed into afault-tolerantprogram for execution on a system which is susceptible to failures. A program is described by a set of atomic actions which perform transformations from states to states. We assume that a fault environment is represented by a programF. Interference by the fault environmentFon the execution of a programPcan then be described as afault-transformationℱ which transformsPinto a program ℱ(P). This is proved to be equivalent to the programP□PF, wherePFis derived fromPandF, and □ defines the union of the sets of actions ofPandFP. A recovery transformation ℛ transformsPinto a program ℛ(P) =P□Rby adding a set ofrecovery actions R, called arecovery program. If the system isfailstopand faults do not affect recovery actions, we have ℱ(ℛ(P))=ℱ(P)□R=P□PF□RWe illustrate this approach to fault-tolerant programming by considering the problem of designing a protocol that guarantees reliable communication from a sender to a receiver in spite of faults in the communication channel between them.