Search

A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are labeled with regular expressions over the alphabet. RGPs model navigational queries for graph databases called conjunctive regular path queries (CRPQs). A match of a CRPQ in the database is witnessed by a special navigational homomorphism of the corresponding RGP to the database. We study the complexity of deciding the existence of a homomorphism between two RGPs. Such homomorphisms model a strong type of containment between the two corresponding CRPQs. We show that this problem can be solved by an EXPTIME algorithm (while general query containmement in this context is EXPSPACE-complete). We also study the problem for restricted RGPs over a unary alphabet, that arise from some applications like XPath or SPARQL. For this case, homomorphism-based CRPQ containment is in NP. We prove that certain interesting cases are in fact polynomial-time solvable., 15 pages. Short version appeared in the proceedings of the 15th Conference on Computability in Europe (CIE 2019)

Metaheuristics are found to be efficient in different applications where the use of exact algorithms becomes short-handed. In the last decade, many of these algorithms have been introduced and used in a wide range of applications. Nevertheless, most of those approaches share similar components leading to a concern related to their novelty or contribution. Thus, in this paper, a pool template is proposed and used to categorize algorithm components permitting to analyze them in a structured way. We exemplify its use by means of continuous optimization metaheuristics, and provide some measures and methodology to identify their similarities and novelties. Finally, a discussion at a component level is provided in order to point out possible design differences and commonalities.

Machine Learning (ML) solutions are nowadays distributed, according to the so-called server/worker architecture. One server holds the model parameters while several workers train the model. Clearly, such architecture is prone to various types of component failures, which can be all encompassed within the spectrum of a Byzantine behavior. Several approaches have been proposed recently to tolerate Byzantine workers. Yet all require trusting a central parameter server. We initiate in this paper the study of the ``general'' Byzantine-resilient distributed machine learning problem where no individual component is trusted. We show that this problem can be solved in an asynchronous system, despite the presence of $\frac{1}{3}$ Byzantine parameter servers and $\frac{1}{3}$ Byzantine workers (which is optimal). We present a new algorithm, ByzSGD, which solves the general Byzantine-resilient distributed machine learning problem by relying on three major schemes. The first, Scatter/Gather, is a communication scheme whose goal is to bound the maximum drift among models on correct servers. The second, Distributed Median Contraction (DMC), leverages the geometric properties of the median in high dimensional spaces to bring parameters within the correct servers back close to each other, ensuring learning convergence. The third, Minimum-Diameter Averaging (MDA), is a statistically-robust gradient aggregation rule whose goal is to tolerate Byzantine workers. MDA requires loose bound on the variance of non-Byzantine gradient estimates, compared to existing alternatives (e.g., Krum). Interestingly, ByzSGD ensures Byzantine resilience without adding communication rounds (on a normal path), compared to vanilla non-Byzantine alternatives. ByzSGD requires, however, a larger number of messages which, we show, can be reduced if we assume synchrony., This is a merge of arXiv:1905.03853 and arXiv:1911.07537; arXiv:1911.07537 will be retracted

Cloud computing enables users to remove the necessity of the need of local hardware architecture, which removes the burden of the users from high computation costs. Therefore, it has attracted much attention and research has been conducted heavily on it. To protect users' privacy, data is usually encrypted prior to being sent to the cloud server. New cryptographic primitive such as public-key encryption with equality test (PKEET) has been introduced to make it more practical. In PKEET, users can test whether the underlying messages of two ciphertexts encrypted under different public keys are equal or not without the need to decrypt those ciphertexts. This is a very useful tool, especially for the cloud database, since PKEET mainly focuses on the equality test between two ciphertexts. However, in practice, the cloud server may need to verify the equivalence among more than two ciphertexts. This leads to disclosing unnecessary information of users and redundant computation cost will also occur when using traditional PKEET schemes. How to make this more efficient and practical remains an interesting research problem. In this paper, to solve the aforementioned problems by providing a novel concept of public-key encryption with multi-ciphertext equality test (PKE-MET).

Large-scale software verification relies critically on the use of compositional languages, semantic models, specifications, and verification techniques. Recent work on certified abstraction layers synthesizes game semantics, the refinement calculus, and algebraic effects to enable the composition of heterogeneous components into larger certified systems. However, in existing models of certified abstraction layers, compositionality is restricted by the lack of encapsulation of state. In this paper, we present a novel game model for certified abstraction layers where the semantics of layer interfaces and implementations are defined solely based on their observable behaviors. Our key idea is to leverage Reddy's pioneer work on modeling the semantics of imperative languages not as functions on global states but as objects with their observable behaviors. We show that a layer interface can be modeled as an object type (i.e., a layer signature) plus an object strategy. A layer implementation is then essentially a regular map, in the sense of Reddy, from an object with the underlay signature to that with the overlay signature. A layer implementation is certified when its composition with the underlay object strategy implements the overlay object strategy. We also describe an extension that allows for non-determinism in layer interfaces. After formulating layer implementations as regular maps between object spaces, we move to concurrency and design a notion of concurrent object space, where sequential traces may be identified modulo permutation of independent operations. We show how to express protected shared object concurrency, and a ticket lock implementation, in a simple model based on regular maps between concurrent object spaces.

The resilience of cyberphysical systems to denial-of-service (DoS) and integrity attacks is studied in this paper. The cyberphysical system is modeled as a linear structured system, and its resilience to an attack is interpreted in a graph theoretical framework. The structural resilience of the system is characterized in terms of unmatched vertices in maximum matchings of the bipartite graph and connected components of directed graph representations of the system under attack. We first present conditions for the system to be resilient to DoS attacks when an adversary may block access or turn off certain inputs to the system. We extend this analysis to characterize resilience of the system when an adversary might additionally have the ability to affect the implementation of state-feedback control strategies. This is termed an integrity attack. We establish conditions under which a system that is structurally resilient to a DoS attack will also be resilient to a certain class of integrity attacks. Finally, we formulate an extension to the case of switched linear systems, and derive conditions for such systems to be structurally resilient to a DoS attack., Comment: Accepted to the European Journal of Control

Several formal systems, such as resolution and minimal model semantics, provide a framework for logic programming. In this paper, we will survey the use of structural proof theory as an alternative foundation. Researchers have been using this foundation for the past 35 years to elevate logic programming from its roots in first-order classical logic into higher-order versions of intuitionistic and linear logic. These more expressive logic programming languages allow for capturing stateful computations and rich forms of abstractions, including higher-order programming, modularity, and abstract data types. Term-level bindings are another kind of abstraction, and these are given an elegant and direct treatment within both proof theory and these extended logic programming languages. Logic programming has also inspired new results in proof theory, such as those involving polarity and focused proofs. These recent results provide a high-level means for presenting the differences between forward-chaining and backward-chaining style inferences. Anchoring logic programming in proof theory has also helped identify its connections and differences with functional programming, deductive databases, and model checking., To appear in Theory and Practice of Logic Programming (TPLP)

Toward combating the malicious rumor spreading on online social networks, we discuss a hybrid control strategy that combines a continuous truth spreading method and an impulsive rumor blocking method in this article. In this strategy, the truth is introduced as an anti-rumor to compete with the rumor while the rumor-infected users would be quarantined with a limited isolation period. The stability of the rumor-free equilibrium of the rumor-truth propagation system is analyzed and conditions to reach uniform asymptotic stability as well as global exponential stability are obtained. For the endemic case, the conditions under which rumor would persist uniformly are obtained. An optimal hybrid control problem is formulated to address the tradeoff between restraining rumor and minimizing the cost of control. The necessary conditions for optimal system and the structure of optimal hybrid control are obtained. Numerical simulations are carried out to illustrate the theoretical results and evaluate the potential roles of the hybrid control strategy.

As the current society is increasingly facing major challenges from extremism and terrorism, protecting key urban public facilities and important targets from destruction is an important challenge facing the security departments of all countries. Based on real scene, this paper conducts researches on anti-terrorism security game algorithms and emergency response models in response to the three key links of before, during and after terrorist attacks. First of all, this paper constructs a multi-round joint attack game and emergency response model based on cooperation, establishes the optimization problem of solving the defender’s optimal strategy in mathematical form, and then obtains the optimal defense strategy. Secondly, in response to the fact that terrorists are not completely rational, a new hybrid model is constructed to propose an efficient allocation and scheduling algorithm for safe resources in response to terrorist attacks. Thirdly, a model of crowd evacuation strategy after a terrorist attack is built based on the problem of crowd evacuation in multiple rounds of premeditated cooperative attacks. Finally, taking the area of the first ring of a certain city as a real scene, a complete game system of the whole process is constructed, and the game effectiveness evaluation of the existing security resource allocation scheme in the first ring area is carried out. Through the research of this thesis, the author puts forward some new technical ideas for the current society’s anti-terrorism governance, and hopes to provide some technical references for the decision-making of security agencies.

Verifying imperative programs is hard. A key difficulty is that the specification of what an imperative program does is often intertwined with details about pointers and imperative state. Although there are a number of powerful separation logics that allow the details of imperative state to be captured and managed, these details are complicated and reasoning about them requires significant time and expertise. In this paper, we take a different approach: a memory-safe type system that, as part of type-checking, extracts functional specifications from imperative programs. This disentangles imperative state, which is handled by the type system, from functional specifications, which can be verified without reference to pointers. A key difficulty is that sometimes memory safety depends crucially on the functional specification of a program; e.g., an array index is only memory-safe if the index is in bounds. To handle this case, our specification extraction inserts dynamic checks into the specification. Verification then requires the additional proof that none of these checks fail. However, these checks are in a purely functional language, and so this proof also requires no reasoning about pointers.

To propose a model where match outcome is predicted ball by ball at the start of the second inning. Our methodology not only incorporates the dynamically updating game context as the game progresses, but also includes the relative strength between the two teams playing the match. We used 692 matches from all seasons (2008–2018) to train our model, and we used all 59 matches from the current season (2019) to test its performance. Here we have engineered 11 players and 10 bowlers, and all their metrics are tracked as a function of each ball of each over throughout the match during the second inning, also keeping in the consideration of dynamically changing target score as one of the attributes. Initially, we tried Logistic Regression, Naive Bayes, K-Nearest Neighbour (KNN), Support Vector Machine, Decision Tree, Random Forest, Boosting, Bagging, and Gradient Boosting with an accuracy of 76.47%(+/–3.77%). With deep learning, we tried the various flavours of LSTM and GRU like vanilla, Bidirectional and stacked to train our models and the results found are very impressive with an accuracy of 76.13%(+/–2.59%). All of these flavors were tested using various approaches such as one-to-one sequencing, one-to-many sequencing, many-to-one sequencing, and many-to-many sequencing, which are discussed in this paper. An accurate prediction of how many runs a batsman is likely to score and how many wickets a bowler is likely to take in a match will help the team management select the best players for each match.

As quantum computers become real, it is high time we come up with effective techniques that help programmers write correct quantum programs. In classical computing, formal verification and sound static type systems prevent several classes of bugs from being introduced. There is a need for similar techniques in the quantum regime. Inspired by Hoare Type Theory in the classical paradigm, we propose Quantum Hoare Types by extending the Quantum IO Monad by indexing it with pre- and post-conditions that serve as program specifications. In this paper, we introduce Quantum Hoare Type Theory (QHTT), present its syntax and typing rules, and demonstrate its effectiveness with the help of examples. QHTT has the potential to be a unified system for programming, specifying, and reasoning about quantum programs. This is a work in progress., Comment: In Proceedings QPL 2020, arXiv:2109.01534. See expanded version at arXiv:2012.02154

Two nature-inspired computing techniques, i.e. the Firefly and the controlled Genetic Algorithm in a restricted divergence environment has been combined to propose an improved Clinical Decision Support System (CDSS) query optimizer. The proposed model is intended to get better query execution plan which will detract the input-output, processing and communication lust for the execution of the CDSS queries. The amalgamated use of the proposed CDSS query optimizer framework will yield substantial variation in two consecutive generations which will efficaciously resolve the slow convergence problem of the controlled Genetic Algorithm. Furthermore, the results of the proposed CDSS query optimizer are tested against the effects of other genetic algorithm based CDSS query optimizers. It is experimentally found that the results produced using RDFG_CDQO are 13%, 10%, 7% and 3.5% better than the outcomes of the other CDSS query optimizers designed using simple, novel, restricted and entropy-based restricted genetic algorithm respectively. To get the best possible solution using RDFG_CDQO, the value of divergence rate should be set up to 50%. Furthermore, to statistically approve the proposed framework, the results obtained using RDFG_CDQO are validated using different measures of regression analysis viz. assumption of linearity, independence, and constant variance.

International audience; This paper presents a novel formal semantics, mechanized in Coq, for a large, sequential subset of the LLVM IR. In contrast to previous approaches, which use relationally-specified operational semantics, this new semantics is based on monadic interpretation of interaction trees, a structure that provides a more compositional approach to defining language semantics while retaining the ability to extract an executable interpreter. Our semantics handles many of the LLVM IR's non-trivial language features and is constructed modularly in terms of event handlers, including those that deal with nondeterminism in the specification. We show how this semantics admits compositional reasoning principles derived from the interaction trees equational theory of weak bisimulation, which we extend here to better deal with nondeterminism, and we use them to prove that the extracted reference interpreter faithfully refines the semantic model. We validate the correctness of the semantics by evaluating it on unit tests and LLVM IR programs generated by HELIX.

In practice, there are numerous settings where mutually distrusting parties need to perform distributed computations on their private inputs. For instance, participants in a first-price sealed-bid online auction do not want their bids to be disclosed. This problem can be addressed using secure multi-party computation (MPC), where parties can evaluate a publicly known function on their private inputs by executing a specific protocol that only reveals the correct output, but nothing else about the private inputs. Such distributed computations performed over the Internet are susceptible to remote hacks that may take place during the computation. As a consequence, sensitive data such as private bids may leak. All existing MPC protocols do not provide any protection against the consequences of such remote hacks. We present the first MPC protocols that protect the remotely hacked parties’ inputs and outputs from leaking. More specifically, unless the remote hack takes place before the party received its input or all parties are corrupted, a hacker is unable to learn the parties’ inputs and outputs, and is also unable to modify them. We achieve these strong (privacy) guarantees by utilizing the fact that in practice parties may not be susceptible to remote attacks at every point in time, but only while they are online, i.e. able to receive messages. To this end, we model communication via explicit channels. In particular, we introduce channels with an airgap switch (disconnect-able by the party in control of the switch), and unidirectional data diodes. These channels and their isolation properties, together with very few, similarly simple and plausibly remotely unhackable hardware modules serve as the main ingredient for attaining such strong security guarantees. In order to formalize these strong guarantees, we propose the UC with Fortified Security (UC#) framework, a variant of the Universal Composability (UC) framework.

Introduction. The organization of branches and repetitions in the context of logical programming is considered by an example of the Prolog language. The fundamental feature of the program in a logical programming language is the fact that a computer must solve a problem by reasoning like a human. Such a program contains a description of objects and relations between them in the language of mathematical logic. At the same time, the software implementation of branching and repetition remains a challenge in the absence of special operators for the indicated constructions in the logical language. The objectives of the study are to identify the most effective ways to solve problems using branching and repetition by means of the logic programming language Prolog, as well as to demonstrate the results obtained by examples of computational problems. Materials and Methods. An analysis of the literature on the subject of the study was carried out. Methods of generalization and systematization of knowledge, of the program testing, and analysis of the program execution were used. Results. Constructions of branching and repetition organization in a Prolog program are proposed. To organize repetitions, various options for completing a recursive cycle when solving problems are given. Discussion and Conclusions. The methods of organizing branches and repetitions in the logic programming language Prolog are considered. All these methods are illustrated by examples of solving computational problems. The results obtained can be used in the further development of the recursive predicates in logical programming languages, as well as in the educational process when studying logical programming in the Prolog language. The examples of programs given in the paper provide using them as a technological basis for programming branches and repetitions in the logic programming language Prolog.

In various provers and deductive verification tools, logical transformations are used extensively in order to reduce a proof task into a number of simpler tasks. Logical transformations are often part of the trusted base of such tools. In this paper, we develop a framework to improve confidence in their results. We follow a modular and skeptical approach: transformations are instrumented independently of each other and produce certificates that are checked by a third-party tool. Logical transformations are considered in a higher-order logic, with type polymorphism and built-in theories such as equality and integer arithmetic. We develop a language of proof certificates for them and use it to implement the full chain of certificate generation and certificate verification., Comment: In Proceedings PxTP 2021, arXiv:2107.01544

International journal on software tools for technology transfer (2021). doi:10.1007/s10009-021-00633-z, Published by Springer, Berlin; Heidelberg [u.a.]

Advancement in deep neural networks have made it possible to compose music that mimics music composition by humans. The capacity of deep learning architectures in learning musical style from arbitrary musical corpora have been explored in this paper. The paper proposes a method for generated from the estimated distribution. Musical chords have been extracted for various instruments to train a sequential model to generate the polyphonic music on some selected instruments. We demonstrate a simple method comprising a sequential LSTM models to generate polyphonic music. The results of the model evaluation show that generated music is pleasant to hear and is similar to music played by humans. This has great application in entertainment industry which enables music composers to generate variety of creative music.

Privacy protection is an essential part of information security. The use of shared resources demands more privacy and security protection, especially in cloud computing environments. Side-channel attacks based on CPU cache utilize shared CPU caches within the same physical device to compromise the system’s privacy (encryption keys, program status, etc.). Information is leaked through channels that are not intended to transmit information, jeopardizing system security. These attacks have the characteristics of both high concealment and high risk. Despite the improvement in architecture, which makes it more difficult to launch system intrusion and privacy leakage through traditional methods, side-channel attacks ignore those defenses because of the shared hardware. Difficult to be detected, they are much more dangerous in modern computer systems. Although some researchers focus on the survey of side-channel attacks, their study is limited to cryptographic modules such as Elliptic Curve Cryptosystems. All the discussions are based on real-world applications (e.g., Curve25519), and there is no systematic analysis for the related attack and security model. Firstly, this paper compares different types of cache-based side-channel attacks. Based on the comparison, a security model is proposed. The model describes the attacks from four key aspects, namely, vulnerability, cache type, pattern, and range. Through reviewing the corresponding defense methods, it reveals from which perspective defense strategies are effective for side-channel attacks. Finally, the challenges and research trends of CPU cache-based side-channel attacks in both attacking and defending are explored. The systematic analysis of CPU cache-based side-channel attacks highlights the fact that these attacks are more dangerous than expected. We believe our survey would draw developers’ attention to side-channel attacks and help to reduce the attack surface in the future.

NewHope cryptosystem is one of the second-round submissions of the National Institute of Standards and Technology post-quantum cryptography standardization process, which is a suite of two key encapsulation mechanisms based on the ring-learning with errors (LWE) problem. It has received much attention from the research community due to its small key size and high efficiency. Recently, three key mismatch attacks are proposed against NewHope under the condition of key reuse. They do not solve the ring-LWE instance directly but exploit the leakage of secret information. As far as we know, the best result is given by Okada et al. ((2020) Improving Key Mismatch Attack on NewHope with Fewer Queries. In Proc. of the 25th Australasian Conf. on Information Security and Privacy, Perth, WA, Australia, November 30–December 2, pp. 505–524. Springer Cham, Switzerland), which recovers the whole secret with a success probability of $97\%$ and $233,803$ average queries. In this paper, we further improve the key mismatch attack of NewHope by reducing the average queries to $106,577$ and raising the success probability to $100\%$. Moreover, we analyze the key mismatch attack without key reuse for the first time and we propose a combinatorial attack against NewHope1024. The total complexity of the combinatorial attack is $2^{253}$, which is lower than the complexity of primal attack and the claimed security strength of NewHope1024.

We study a framework for the specification and validation of dynamic reconfigurable systems. The framework is based on configuration logic for the description of architecture styles which are families of architectures sharing common connectivity features. We express specifications in the Temporal Configuration Logic (TCL), a linear time temporal logic built from atomic formulas characterizing system configurations and temporal modalities. Two non-trivial benchmarks are introduced to show the adequacy of TCL for the specification of dynamic reconfigurable systems. We study an effective model-checking procedure based on SMT techniques for a non-trivial fragment of TCL which has been implemented in a prototype runtime verification tool. We provide preliminary experimental results illustrating the capabilities of the tool on the considered benchmark systems.

Intervals have become prominent in data management as they are the main data structure to represent a number of key data types such as temporal or genomic data. Yet, there exists no solution to compactly store and efficiently query big interval data. In this paper we introduce CINTIA—the Checkpoint INTerval Index Array—an efficient data structure to store and query interval data, which achieves high memory locality and outperforms state-of-the art solutions. We also propose a low-latency, Big Data system that implements CINTIA on top of a popular distributed file system and efficiently manages large interval data on clusters of commodity machines. Our system can easily be scaled-out and was designed to accommodate large delays between the various components of a distributed infrastructure. We experimentally evaluate the performance of our approach on several datasets and show that it outperforms current solutions by several orders of magnitude in distributed settings.

In the modern world, several areas of our lives can be improved, in the form of diverse additional dimensions, in terms of quality, by machine learning. When building machine learning models, open data are often used. Although this trend is on the rise, the monetary losses since the attacks on machine learning models are also rising. Preparation is, thus, believed to be indispensable in terms of embarking upon machine learning. In this field of endeavor, machine learning models may be compromised in various ways, including poisoning attacks. Assaults of this nature involve the incorporation of injurious data into the training data rendering the models to be substantively less accurate. The circumstances of every individual case will determine the degree to which the impairment due to such intrusions can lead to extensive disruption. A modus operandi is proffered in this research as a safeguard for machine learning models in the face of the poisoning menace, envisaging a milieu in which machine learning models make use of data that emanate from numerous sources. The information in question will be presented as training data, and the diversity of sources will constitute a barrier to poisoning attacks in such circumstances. Every source is evaluated separately, with the weight of each data component assessed in terms of its ability to affect the precision of the machine learning model. An appraisal is also conducted on the basis of the theoretical effect of the use of corrupt data as from each source. The extent to which the subgroup of data in question can undermine overall accuracy depends on the estimated data removal rate associated with each of the sources described above. The exclusion of such isolated data based on this figure ensures that the standard data will not be tainted. To evaluate the efficacy of our suggested preventive measure, we evaluated it in comparison with the well-known standard techniques to assess the degree to which the model was providing accurate conclusions in the wake of the change. It was demonstrated during this test that when the innovative mode of appraisal was applied, in circumstances in which 17% of the training data are corrupt, the degree of precision offered by the model is 89%, in contrast to the figure of 83% acquired through the traditional technique. The corrective technique suggested by us thus boosted the resilience of the model against harmful intrusion.

Reduct of decision systems is the topic that has been attracting the interest of many researchers in data mining and machine learning for more than two decades. So far, many algorithms for finding reduct of decision systems by rough set theory have been proposed. However, most of the proposed algorithms are heuristic algorithms that find one reduct with the best classification quality. The complete study of properties of reduct of decision systems is limited. In this paper, we discover equivalence properties of reduct of consistent decision systems related to a Sperner-system. As the result, the study of the family of reducts in a consistent decision system is the study of Sperner-systems.

Among the challenges of the big data era, the analysis of high-dimensional data is still an open research area. As a result, several multidimensional projection techniques have been developed to reduce data dimensionality, becoming important visualization and visual analytics tools. In order to ensure the quality of projections, it is necessary to assess the low-dimensional embeddings by using different dataset configurations as input and analyzing evaluation metrics. However, it is not clear to the user how factors such as the number of dimensions, instances, or clusters, can affect the projection mapping and its quality regarding different projection techniques and assessment metrics. The research reported in this paper aims to clarify how much these factors affect each response variable via performance evaluation planning. We present an evaluation approach, supported by factorial design, that carries out a complete analysis, in the sense of measuring all possible combinations of all the input factors. The results of the analyses of local and global structure preservation in the projections yield a better understanding of how distinct dataset properties can influence the choice of projections based on quality metrics results.

Self-driving cars over the last decade have achieved significant progress like driving millions of miles without any human intervention. However, behavioral safety in applying deep-neural-network-based (DNN based) systems for self-driving cars could not be guaranteed. Several real-world accidents involving self-driving cars have already happened, some of which have led to fatal collisions. In this paper, we present a novel and automated technique for verifying steering angle safety for self-driving cars. The technique is based on deep learning verification (DLV), which is an automated verification framework for safety of image classification neural networks. We extend DLV by leveraging neuron coverage and slack relationship to solve the judgement problem of predicted behaviors, and thus, to achieve verification of steering angle safety for self-driving cars. We evaluate our technique on the NVIDIA’s end-to-end self-driving architecture, which is a crucial ingredient in many modern self-driving cars. Experimental results show that our technique can successfully find adversarial misclassifications (i.e., incorrect steering decisions) within given regions if they exist. Therefore, we can achieve safety verification (if no misclassification is found for all DNN layers, in which case the network can be said to be stable or reliable w.r.t. steering decisions) or falsification (in which case the adversarial examples can be used to fine-tune the network).

In the light of standardization, the model-driven engineering (MDE) is becoming increasingly important for the development of DSLs, in addition to traditional approaches based on grammar formalisms. Metamodels define the abstract syntax and static semantics of a DSL and can be created by using the language concepts of the Meta Object Facility (MOF) or by defining a UML profile.Both metamodels and UML profiles are often provided for standardized DSLs, and the mappings of metamodels to UML profiles are usually specified informally in natural language, which also applies for the static semantics of metamodels and/or UML profiles, which has the disadvantage that ambiguities can occur, and that the static semantics must be manually translated into a machine-processable language.To address these weaknesses, we propose a new automated approach for deriving a UML profile from the metamodel of a DSL. One novelty is that subsetting or redefining metaclass attributes are mapped to stereotype attributes whose values are computed at runtime via automatically created OCL expressions. The automatic transfer of the static semantics of a DSL to a UML profile is a further contribution of our approach. Our DSL Metamodeling and Derivation Toolchain (DSL-MeDeTo) implements all aspects of our proposed approach in Eclipse. This enabled us to successfully apply our approach to the two DSLs Test Description Language (TDL) and Specification and Description Language (SDL).

Exact query on big data is a challenging task due to the large numbers of autonomous data sources. In this paper, an efficient method is proposed to select sources on big data for approximate query. A gain model is presented for source selection by considering information coverage and quality provided by sources. Under this model, the source selection problem is formalized into two optimization problems. Because of the NP-hardness of proposed problems, two approximate algorithms are devised to solve them respectively, and their approximate ratios and complexities are analyzed. To further improve efficiency, a randomized method is developed for gain estimation. Based on it, the time complexities of improved algorithms are sub-linear in the number of data item. Experimental results show high efficiency and scalability of proposed algorithms.

Heart-related diseases or Cardiovascular Diseases (CVDs) are the main reason for a huge number of death in the world over the last few decades and has emerged as the most life-threatening disease, not only in India but in the whole world. So, there is a need fora reliable, accurate, and feasible system to diagnose such diseases in time for proper treatment. Machine Learning algorithms and techniques have been applied to various medical datasets to automate the analysis of large and complex data. Many researchers, in recent times, have been using several machine learning techniques to help the health care industry and the professionals in the diagnosis of heart-related diseases. Heart is the next major organ comparing to the brain which has more priority in the Human body. It pumps the blood and supplies it to all organs of the whole body. Prediction of occurrences of heart diseases in the medical field is significant work. Data analytics is useful for prediction from more information and it helps the medical center to predict various diseases. A huge amount of patient-related data is maintained on monthly basis. The stored data can be useful for the source of predicting the occurrence of future diseases. Some of the data mining and machine learning techniques are used to predict heart diseases, such as Artificial Neural Network (ANN), Random Forest,and Support Vector Machine (SVM).Prediction and diagnosingof heart disease become a challenging factor faced by doctors and hospitals both in India and abroad. To reduce the large scale of deaths from heart diseases, a quick and efficient detection technique is to be discovered. Data mining techniques and machine learning algorithms play a very important role in this area. The researchers accelerating their research works to develop software with thehelp of machine learning algorithms which can help doctors to decide both prediction and diagnosing of heart disease. The main objective of this research project is to predict the heart disease of a patient using machine learning algorithms.

Various machine learning techniques exist to perform regression on temporal data with concept drift occurring. However, there are numerous nonstationary environments where these techniques may fail to either track or detect the changes. This study develops a genetic programming-based predictive model for temporal data with a numerical target that tracks changes in a dataset due to concept drift. When an environmental change is evident, the proposed algorithm reacts to the change by clustering the data and then inducing nonlinear models that describe generated clusters. Nonlinear models become terminal nodes of genetic programming model trees. Experiments were carried out using seven nonstationary datasets and the obtained results suggest that the proposed model yields high adaptation rates and accuracy to several types of concept drifts. Future work will consider strengthening the adaptation to concept drift and the fast implementation of genetic programming on GPUs to provide fast learning for high-speed temporal data.

The number of sentence pairs in the bilingual corpus is a key to translation accuracy in computational machine translations. However, if the amount goes beyond a certain degree, the increasing number of cases has less impact on the translation while the construction of translation systems requires a considerable amount of time and energy, thus preventing the development of a statistical translation by the computer. This article offers a number of classifications for measuring the amount of information for each pair of sentences, using the Heuristic Bilingual Graph Corpus Network (HBGCN) to form an improved method of corpus selection that takes the difference between the first amount of information between the pairs of sentences into account. Using a graphic-based selector method as a training set, they achieve a close translation result through our experiments with the whole body and achieve better results than basic results for the following based on the Document Inverse Frequency (DIF) ranking approach.

New services such as autonomous driving, the connectivity of the traffic infrastructure and the tight coupling of user operated smart devices with the vehicle have significantly increased the demand for cryptographic protection in the automobile. To provide a secure environment for the calculation and verification of cryptographic material, automotive microcontrollers now frequently integrate Hardware Security Modules (HSM), special well-protected co-processors, which are protected against manipulation and external access. HSMs use special hardware accelerators to provide the required cryptographic services. While these accelerators provide good performance, they limit flexibility and updatability. In addition, as more services require cryptographic protection, the amount of key material that needs to be managed by the HSM also increases, turning the limited protected memory of the HSM into a bottleneck. This paper presents a framework that uses the safety mechanisms of a microcontroller to achieve both HSM-equivalent security through software solutions, while providing an equivalent level of functionality. Furthermore, the proposed framework provides crypto-agility, as the security stack can be updated if desired. In order to verify the functionality, the presented framework is implemented and evaluated on an Infineon AURIX TC399 and compared with the integrated HSM.

Secret key leakage has become a security threat in computer systems, and it is crucial that cryptographic schemes should resist various leakage attacks, including the continuous leakage attacks. In the literature, some research progresses have been made in designing leakage resistant cryptographic primitives, but there are still some remaining issues unsolved, e.g. the upper bound of the permitted leakage is fixed. In actual applications, the leakage requirements may vary; thus, the leakage parameter with fixed size is not sufficient against various leakage attacks. In this paper, we introduce some novel idea of designing a continuous leakage-amplified public-key encryption scheme with security against chosen-ciphertext attacks. In our construction, the leakage parameter can have an arbitrary length, i.e. the length of the permitted leakage can be flexibly adjusted according to the specific leakage requirements. The security of our proposed scheme is formally proved based on the classic decisional Diffie–Hellman assumption.

Feature selection in logical analysis of data (LAD) can be cast into a set covering problem. In this paper, extending the results on feature selection for binary classification using LAD, we present a mathematical model that selects a minimum set of necessary features for multi-class datasets and develop a heuristic algorithm that is both memory and time efficient for this model correspondingly. The utility of the algorithm is illustrated on a small example and the superiority of our work is demonstrated through experiments on 6 real-life multi-class datasets from UCI repository.

Dynamic flexible job-shop scheduling (DFJSS) is a challenging combinational optimization problem that takes the dynamic environment into account. Genetic programming hyperheuristics (GPHH) have been widely used to evolve scheduling heuristics for job-shop scheduling. A proper selection of the terminal set is a critical factor for the success of GPHH. However, there is a wide range of features that can capture different characteristics of the job-shop state. Moreover, the importance of a feature is unclear from one scenario to another. The irrelevant and redundant features may lead to performance limitations. Feature selection is an important task to select relevant and complementary features. However, little work has considered feature selection in GPHH for DFJSS. In this article, a novel two-stage GPHH framework with feature selection is designed to evolve scheduling heuristics only with the selected features for DFJSS automatically. Meanwhile, individual adaptation strategies are proposed to utilize the information of both the selected features and the investigated individuals during the feature selection process. The results show that the proposed algorithm can successfully achieve more interpretable scheduling heuristics with fewer unique features and smaller sizes. In addition, the proposed algorithm can reach comparable scheduling heuristic quality with much shorter training time.

This paper aims at developing new models to combine the best of two paradigms: the performance of ensembles and the transparency of choice models. Specifically, the work explores several blind methods to build ensembles of single choice-based models. They were fit using a dataset that includes rational, emotional and attentional variables, all of them gathered from humans during a choice task. Two main strategies, 1-Learner and N-Learners type ensembles, were analyzed in terms of their accuracy as well as frequency of best-model metrics. The results point out the superior performance of N-Learners ensembles and show the potential of personalized arrangements.

Nowadays, crowdsourcing gains an increasing popularity as it can be adopted to solve many challenging question answering tasks that are easy for humans but difficult for computers. Due to the variety in the quality of users, it is important to infer not only the underlying ground truth of these tasks but also the users ability from the answers given by users. This problem is called Ground Truth Inference and has been studied for many years. However, since the answers collected from the users may contain sensitive information, ground truth inference raises serious privacy concern. Due to this reason, the problem of ground truth inference under local differential privacy (LDP) model has been recently studied. However, this problem is still not well understood and even some basic questions have not been solved yet. First, it is still unknown what is the average error of the private estimators to the underlying ground truth. Secondly, we do not know whether we can infer the ability of each user under LDP model and what is the estimation error w.r.t. the underlying users ability. Finally, previous work only shows that their methods have better performance than the private major voting algorithm through experiments. However, there is still no theoretically result which shows this priority formally or mathematically. In this paper, we partially solve these problems by studying the ground truth inference problem under local attribute differential privacy (LADP) model, which is a relaxation of LDP model, and propose a new algorithm called private Dawid-Skene method, which is motivated by the classical Dawid-Skene method. Specifically, we first provide the estimation errors for both ability of users and the ground truth under some assumptions of the problem if the algorithm start with some appropriate initial vector. Moreover, we propose an explicit instance and show that the estimation error of the ground truth achieved by the private major voting algorithm is always greater than the error achieved by our method.

This paper describes an AI that uses construction grammar (CG)—a means of knowledge representation for deep understanding of text. The proposed improvements aim at more versatility of the text form and meaning knowledge structure, as well as for intelligent choosing among possible parses. Along with the improvements, computational CG techniques that form the implementation basis are explained. Evaluation experiments utilize a Winograd schema (WS)—a major test for AI—dataset and compare the implementation with state-of-the-art ones. Results have demonstrated that compared with such techniques as deep learning, the proposed CG approach has a higher potential for the task of anaphora resolution involving deep understanding of the natural language.

This paper proposes a new temporal logic named Unified Temporal Logic (UTL). First, the syntax and semantics of UTL are inductively defined. Further, logic laws in UTL are formalized and proved. Moreover, the normal forms of UTL formulas are defined and proved. To illustrate how to describe properties with UTL, an example of an elevator control system is given. In general, UTL combines the characteristics of Linear Temporal Logic (LTL) and Propositional Projection Temporal Logic (PPTL). So properties involving the “until” construct in LTL and the “chop” construct in PPTL can easily be represented in UTL. In addition, both finite and infinite models (intervals) are supported. With UTL, we are able to specify and verify some practical properties which cannot easily be formalized in LTL and PPTL.

Rust is a relatively new programming language that has gained significant traction since its v1.0 release in 2015. Rust aims to be a systems language that competes with C/C++. A claimed advantage of Rust is a strong focus on memory safety without garbage collection. This is primarily achieved through two concepts, namely, reference lifetimes and borrowing . Both of these are well-known ideas stemming from the literature on region-based memory management and linearity / uniqueness . Rust brings both of these ideas together to form a coherent programming model. Furthermore, Rust has a strong focus on stack-allocated data and, like C/C++ but unlike Java, permits references to local variables. Type checking in Rust can be viewed as a two-phase process: First, a traditional type checker operates in a flow-insensitive fashion; second, a borrow checker enforces an ownership invariant using a flow-sensitive analysis. In this article, we present a lightweight formalism that captures these two phases using a flow-sensitive type system that enforces “ type and borrow safety .” In particular, programs that are type and borrow safe will not attempt to dereference dangling pointers. Our calculus core captures many aspects of Rust, including copy- and move-semantics, mutable borrowing, reborrowing, partial moves, and lifetimes. In particular, it remains sufficiently lightweight to be easily digested and understood and, we argue, still captures the salient aspects of reference lifetimes and borrowing. Furthermore, extensions to the core can easily add more complex features (e.g., control-flow, tuples, method invocation). We provide a soundness proof to verify our key claims of the calculus. We also provide a reference implementation in Java with which we have model checked our calculus using over 500B input programs. We have also fuzz tested the Rust compiler using our calculus against 2B programs and, to date, found one confirmed compiler bug and several other possible issues.

Context. In today’s information society with advanced telecommunications through mobile devices and computer networks, it is important to form a variety of virtual organizations and communities. Such virtual associations of people by professional or other interests are designed to quickly solve various tasks: to perform project tasks, create startups to attract investors, network marketing, distance learning, solving complex problems in science, economics and public administration , construction of various Internet services, discussion of political and social processes, etc. Objective of the study is to develop an adaptive Markov recurrent method based on the stochastic approximation of the modified condition of complementary non-rigidity, valid at Nash equilibrium points for solving the problem of game coverage of projects. Method. In this work the multiagent game model for formation of virtual teams of executors of projects on the basis of libraries of subject ontologies is developed. The competencies and abilities of agents required to carry out projects are specified by sets of ontologies. Intelligent agents randomly, simultaneously and independently choose one of the projects at discrete times. Agents who have chosen the same project determine the current composition of the team of its executors. For agents’ teams, a current penalty is calculated for insufficient coverage of competencies by the combined capabilities of agents. This penalty is used to adaptively recalculate mixed player strategies. The probabilities of selecting those teams whose current composition has led to a reduction in the fine for non-coverage of ontologies are increasing. During the repetitive stochastic game, agents will form vectors of mixed strategies that will minimize average penalties for non-coverage of projects. Results. For solve the problem of game coverage of projects, an adaptive Markov recurrent method based on the stochastic approximation of the modified condition of complementary non-rigidity, valid at Nash equilibrium points, was developed. Conclusions. Computer simulation confirmed the possibility of using the stochastic game model to form teams of project executors with the necessary ontological support in conditions of uncertainty. The convergence of the game method is ensured by compliance with the fundamental conditions and limitations of stochastic optimization. The reliability of experimental studies is confirmed by the repeatability of the results obtained for different sequences of random variables.

In order to develop reliable safety standards for 5G sensor networks (SN) and the Internet of Things, appropriate verification tools are needed, including those offering the ability to perform automated symbolic analysis process. The Tamarin prover is one of such software-based solutions. It allows to formally prove security protocols. This paper shows the modus operandi of the tool in question. Its application has been illustrated using an example of an exchange of messages between two agents, with asynchronous encryption. The scheme may be implemented, for instance, in the TLS/DTLS protocol to create a secure cryptographic key exchange mechanism. The aim of the publication is to demonstrate that automated symbolic analysis may be relied upon to model 5G sensor networks security protocols. Also, a use case in which the process of modeling the DTLS 1.2 handshake protocol enriched with the TCP SYN Cookies mechanism, used to preventing DoS attacks, is presented

Enabling smartphones to understand our emotional well-being provides the potential to create personalised applications and highly responsive interfaces. However, this is by no means a trivial task - subjectivity in reporting emotions impacts the reliability of ground-truth information whereas smartphones, unlike specialised wearables, have limited sensing capabilities. In this paper, we propose a new approach that advances emotional state prediction by extracting outlier-based features and by mitigating the subjectivity in capturing ground-truth information. We utilised this approach in a distinctive and challenging use case - happiness detection - and we demonstrated prediction performance improvements of up to 13% in AUC and 27% in F-score compared to the traditional modelling approaches. The results indicate that extreme values (i.e. outliers) of sensor readings mirror extreme values in the reported happiness levels. Furthermore, we showed that this approach is more robust in replicating the prediction model in completely new experimental settings.

This paper presents an analysis on the state of the art of several proposals for algorithmic countermeasures to prevent passive side-channel attacks (SCA) on elliptic curve cryptography (ECC) defined over prime fields. One of the main applications of ECC is in the field of Internet of Things, where the interconnection of devices requires public-key technology with small key sizes and high security levels. Since the secure implementation of ECC on embedded devices involves many challenges for security and efficiency, this work evaluates the trade-offs between security and performance of side-channel attack countermeasures for scalar multiplication algorithms without precomputation. The main contribution is to present a panorama of explicit solutions that may be used for the implementation of ECC mechanisms suitable for embedded devices. In addition to the security problems, some countermeasures are also analyzed.

Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #SAT, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #SAT often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation., Comment: Under consideration in Theory and Practice of Logic Programming (TPLP)

This paper introduces Multi-Region Symbolic Regression (MR-SR), a general framework that divides the original input data space of symbolic regression problems into subspaces (regions), generates different solutions to fit these regions and then combines them. MR-SR has three main components: (1) a strategy for finding the different regions of the data input space; (2) a method for generating the functions for each region; and (3) a strategy for combining the models found by (2). The main contribution of this paper is on how we generate the functions for each region. We model the function generation problem following a multi-objective approach, where each objective corresponds to the quality of the evolved function in a region, and the number of objectives is equal to the number of regions of the data input space. We test MR-SR in two scenarios with different objectives. In the first, we used the new approach to solve the symbolic regression problem with standard GP, with the main objective of reducing error rate. In the second, we took advantage of this method for a different purpose: to reduce the dimensionality of the semantic space of a variation of GP, namely Geometric Semantic Genetic Programming (GSGP). Results in 10 datasets showed that the method using clustering k-means and a model switching strategy—which makes predictions using the best evolved function for the region of interest—obtained better results in 5 out of 10 datasets for GP with 2 regions. For GSGP the framework was less effective due to the lack of diversity of the solutions evolved.

Multi-task learning, as it is understood nowadays, consists of using one single model to carry out several similar tasks. From classifying hand-written characters of different alphabets to figuring out how to play several Atari games using reinforcement learning, multi-task models have been able to widen their performance range across different tasks, although these tasks are usually of a similar nature. In this work, we attempt to widen this range even further, by including heterogeneous tasks in a single learning procedure. To do so, we firstly formally define a multi-network model, identifying the necessary components and characteristics to allow different adaptations of said model depending on the tasks it is required to fulfill. Secondly, employing the formal definition as a starting point, we develop an illustrative model example consisting of three different tasks (classification, regression and data sampling). The performance of this model implementation is then analyzed, showing its capabilities. Motivated by the results of the analysis, we enumerate a set of open challenges and future research lines over which the full potential of the proposed model definition can be exploited., Preprint

Many scientists apply fully dynamic bin packing problem solving for resource allocation of virtual machines in cloud environments. The goal of problem-solving is to reduce the number of allocated hosts (bins) and virtual machines (items) migration rates for reducing energy consumption. This study demonstrates a greedy futuristic algorithm (proposed algorithm) for fully dynamic bin packaging with an average asymptotic approximation ratio of 1.231, better than other existing algorithms. The proposed algorithm identifies inappropriate local selections using special futuristic conditions to prevent them as much as possible. Eventually, suitable choices determine and discard the improper ones. The proposed algorithm illustrates an asymptotic approximation ratio of (t/ (t-1)) OPT, where the value of t depends on the distribution of the arrived and departed items. Also, OPT is the number of bins by an optimal solution. Finally, in experiments of datasets using a maximum utilization of 80% of each bin, the average migration rate is 0.338. Using the proposed method for allocating resources in the cloud environment can allocate hosts to a virtual machine using almost optimal use. This allocation can reduce the cost of maintaining and purchasing hosts. Also, this method can reduce the migration rate of virtual machines. As a result, decreasing migration improves the energy consumption cost in the cloud environment.