Search

We demonstrate how a generic automated theorem prover can be applied to establish the non-orderability of groups. Our approach incorporates various tools such as positive cones, torsions, generalised torsions and cofinal elements., Comment: 35 pages, 0 figures

Writing temporal logic formulae for properties that combine instantaneous events with overlapping temporal phenomena of some duration is difficult in classical temporal logics. To address this issue, in previous work we introduced a new temporal logic with intuitive temporal modalities specifically tailored for the representation of both instantaneous and durative phenomena. We also provided an implementation of a complex event processing system, Phenesthe, based on this logic, that has been applied and tested on a real maritime surveillance scenario. In this work, we extend our temporal logic with two extra modalities to increase its expressive power for handling future formulae. We compare the expressive power of different fragments of our logic with Linear Temporal Logic and dyadic first-order logic. Furthermore, we define correctness criteria for stream processors that use our language. Last but not least, we evaluate empirically the performance of Phenesthe+, our extended implementation, and show that the increased expressive power does not affect efficiency significantly., Comment: In Proceedings GandALF 2023, arXiv:2309.17318

In this paper, we introduce the transition-based feature generator (TFGen) technique, which reads general activity data with attributes and generates step-by-step generated data. The activity data may consist of network activity from packets, system calls from processes or classified activity from surveillance cameras. TFGen processes data online and will generate data with encoded historical data for each incoming activity with high computational efficiency. The input activities may concurrently originate from distinct traces or channels. The technique aims to address issues such as domain-independent applicability, the ability to discover global process structures, the encoding of time-series data, and online processing capability.

We use machine learning to classify examples of braids (or flat braids) as trivial or non-trivial. Our ML takes form of supervised learning using neural networks (multilayer perceptrons). When they achieve good results in classification, we are able to interpret their structure as mathematical conjectures and then prove these conjectures as theorems. As a result, we find new convenient invariants of braids, including a complete invariant of flat braids., Comment: 24 pages

Two recent publications describe realizable Gauss diagrams using conditions stating that the number of chords in certain sets of chords is even or odd. We demonstrate that these descriptions are incorrect by finding multiple counter-examples. However, the idea of having a parity-based description of realizable Gauss diagrams is attractive. We recall that realizability of Gauss diagrams as touch curves can be described via bipartite graphs. We show that realizable Gauss diagrams can be described via bipartite graphs., Comment: arXiv admin note: text overlap with arXiv:2108.02873

Data encryption limits the power and efficiency of queries. Direct processing of encrypted data should ideally be possible to avoid the need for data decryption, processing, and re-encryption. It is vital to keep the data searchable and sortable. That is, some information is intentionally leaked. This intentional leakage technology is known as "querying over encrypted data schemes", which offer confidentiality as well as querying over encrypted data, but it is not meant to provide flexible access control. This paper suggests the use of Ciphertext Policy Attributes Based Encryption (CP-ABE) to address three security requirements, namely: confidentiality, queries over encrypted data, and flexible access control. By combining flexible access control and data confidentiality, CP-ABE can authenticate who can access data and possess the secret key. Thus, this paper identifies how much data leakage there is in order to figure out what kinds of operations are allowed when data is encrypted by CP-ABE.

In this paper, we consider the naive applications of process mining in network traffic comprehension, traffic anomaly detection, and intrusion detection. We standardise the procedure of transforming packet data into an event log. We mine multiple process models and analyse the process models mined with the inductive miner using ProM and the fuzzy miner using Disco. We compare the two types of process models extracted from event logs of differing sizes. We contrast the process models with the RFC TCP state transition diagram and the diagram by Bishop et al. We analyse the issues and challenges associated with process mining in intrusion detection and explain why naive process mining with network data is ineffective.

We report on our success on solving the problem of untangling braids up to length 20 and width 4. We use feed-forward neural networks in the framework of reinforcement learning to train the agent to choose Reidemeister moves to untangle braids in the minimal number of moves.

In this paper, we consider the applications of process mining in intrusion detection. We propose a novel process mining inspired algorithm to be used to preprocess data in intrusion detection systems (IDS). The algorithm is designed to process the network packet data and it works well in online mode for online intrusion detection. To test our algorithm, we used the CSE-CIC-IDS2018 dataset which contains several common attacks. The packet data was preprocessed with this algorithm and then fed into the detectors. We report on the experiments using the algorithm with different machine learning (ML) models as classifiers to verify that our algorithm works as expected; we tested the performance on anomaly detection methods as well and reported on the existing preprocessing tool CICFlowMeter for the comparison of performance., Comment: International Conference on Software Testing, Machine Learning and Complex Process Analysis

The shipping industry is an important component of the global trade and economy, however in order to ensure law compliance and safety it needs to be monitored. In this paper, we present a novel Ship Type classification model that combines vessel transmitted data from the Automatic Identification System, with vessel imagery. The main components of our approach are the Faster R-CNN Deep Neural Network and a Neuro-Fuzzy system with IF-THEN rules. We evaluate our model using real world data and showcase the advantages of this combination while also compare it with other methods. Results show that our model can increase prediction scores by up to 15.4\% when compared with the next best model we considered, while also maintaining a level of explainability as opposed to common black box approaches., Comment: Accepted and presented in RuleML+RR 2021

We use reinforcement learning to tackle the problem of untangling braids. We experiment with braids with 2 and 3 strands. Two competing players learn to tangle and untangle a braid. We interface the braid untangling problem with the OpenAI Gym environment, a widely used way of connecting agents to reinforcement learning problems. The results provide evidence that the more we train the system, the better the untangling player gets at untangling braids. At the same time, our tangling player produces good examples of tangled braids.

The previous VPT 2020 workshop was organized in honour of Professor Alberto Pettorossi on the occasion of his academic retirement from Universit\`a di Roma Tor Vergata. Due to the pandemic the VPT 2020 meeting was cancelled but its proceeding have already appeared in the EPTCS 320 volume. The joint VPT-20-21 event has subsumed the original programme of VPT 2020 and provided an opportunity to meet and celebrate the achievements of Professor Alberto Pettorossi; its programme was further expanded with the newly submitted presentations for VPT 2021. The aim of the VPT workshop series is to provide a forum where people from the areas of program transformation and program verification can fruitfully exchange ideas and gain a deeper understanding of the interactions between those two fields.

Event definitions in Complex Event Processing systems are constrained by the expressiveness of each system's language. Some systems allow the definition of instantaneous complex events, while others allow the definition of durative complex events. While there are exceptions that offer both options, they often lack of intervals relations such as those specified by the Allen's interval algebra. In this paper, we propose a new logic based temporal phenomena definition language, specifically tailored for Complex Event Processing, that allows the representation of both instantaneous and durative phenomena and the temporal relations between them. Moreover, we demonstrate the expressiveness of our proposed language by employing a maritime use case where we define maritime events of interest. Finally, we analyse the execution semantics of our proposed language for stream processing and introduce the `Phenesthe' implementation prototype., Comment: Pre-proceedings paper presented at the 31st International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2021), Tallinn, Estonia, and Virtual, September 7-8, 2021 (arXiv:2107.10160)

Chord diagrams, under the name of Gauss diagrams, are used in low-dimensional topology as an important tool for studying curves or knots. Those Gauss diagrams that correspond to curves or knots are called realizable. The theme of our paper is the fact that realizability of a Gauss diagram can be expressed via its circle graph. Accordingly, one can define and study realizable circle graphs (with realizability of a circle graph understood as realizability of any one of chord diagrams corresponding to the graph). Several studies contain theorems purporting to prove the fact. We check several of these descriptions experimentally and find counterexamples to the descriptions of realizable Gauss diagrams in some of these publications. We formulate new descriptions of realizable circle graphs and present an elegant algorithm for checking if a circle graph is realizable. We enumerate realizable circle graphs for small sizes and comment on these numbers. Then we concentrate on one type of curves, called meanders, and study the circle graphs of their Gauss diagrams., Comment: 25 pages

Ensuring that autonomous space robot control software behaves as it should is crucial, particularly as software failure in space often equates to mission failure and could potentially endanger nearby astronauts and costly equipment. To minimise mission failure caused by software errors, we can utilise a variety of tools and techniques to verify that the software behaves as intended. In particular, distinct nodes in a robotic system often require different verification techniques to ensure that they behave as expected. This paper introduces a method for integrating the various verification techniques that are applied to robotic software, via a First-Order Logic (FOL) specification that captures each node's assumptions and guarantees. These FOL specifications are then used to guide the verification of the individual nodes, be it by testing or the use of a formal method. We also outline a way of measuring our confidence in the verification of the entire system in terms of the verification techniques used.

Penetration testing (or pentesting) is one of the widely used and important methodologies to assess the security of computer systems and networks. Traditional pentesting relies on the domain expert knowledge and requires considerable human effort all of which incurs a high cost. The automation can significantly improve the efficiency, availability and lower the cost of penetration testing. Existing approaches to the automation include those which map vulnerability scanner results to the corresponding exploit tools, and those addressing the pentesting as a planning problem expressed in terms of attack graphs. Due to mainly non-interactive processing, such solutions can deal effectively only with static and simple targets. In this paper, we propose an automated penetration testing approach based on the belief-desire-intention (BDI) agent model, which is central in the research on agent-based processing in that it deals interactively with dynamic, uncertain and complex environments. Penetration testing actions are defined as a series of BDI plans and the BDI reasoning cycle is used to represent the penetration testing process. The model is extensible and new plans can be added, once they have been elicited from the human experts. We report on the results of testing of proof of concept BDI-based penetration testing tool in the simulated environment.

This volume contains a final and revised selection of papers presented at the Seventh International Workshop on Verification and Program Transformation (VPT 2019), which took place in Genova, Italy, on April 2nd, 2019, affiliated with Programming 2019.

We explore an approach to verification of programs via program transformation applied to an interpreter of a programming language. A specialization technique known as Turchin's supercompilation is used to specialize some interpreters with respect to the program models. We show that several safety properties of functional programs modeling a class of cache coherence protocols can be proved by a supercompiler and compare the results with our earlier work on direct verification via supercompilation not using intermediate interpretation. Our approach was in part inspired by an earlier work by E. De Angelis et al. (2014-2015) where verification via program transformation and intermediate interpretation was studied in the context of specialization of constraint logic programs., Comment: In Proceedings VPT 2017, arXiv:1708.06887. The author's extended version is arXiv:1705.06738

This volume contains the proceedings of the Fifth International Workshop on Verification and Program Transformation (VPT 2017). The workshop took place in Uppsala, Sweden, on April 29th, 2017, affiliated with the European Joint Conferences on Theory and Practice of Software (ETAPS). The aim of the VPT workshop series is to provide a forum where people from the areas of program transformation and program verification can fruitfully exchange ideas and gain a deeper understanding of the interactions between those two fields. Seven papers were presented at the workshop. Additionally, three invited talks were given by Javier Esparza (Technische Universit\"at M\"unchen, Germany), Manuel Hermenegildo (IMDEA Software Institute, Madrid, Spain), and Alexey Khoroshilov (Linux Verification Center, ISPRAS, Moscow, Russia).

We explore an approach to verification of programs via program transformation applied to an interpreter of a programming language. A specialization technique known as Turchin's supercompilation is used to specialize some interpreters with respect to the program models. We show that several safety properties of functional programs modeling a class of cache coherence protocols can be proved by a supercompiler and compare the results with our earlier work on direct verification via supercompilation not using intermediate interpretation. Our approach was in part inspired by an earlier work by De E. Angelis et al. (2014-2015) where verification via program transformation and intermediate interpretation was studied in the context of specialization of constraint logic programs., Comment: Fifth International Workshop on Verification and Program Transformation (VPT-2017), April 29th, 2017, Uppsala, Sweden, 37 pages

This volume contains the revised versions of papers presented at the Fourth International Workshop on Verification and Program Transformation (VPT 2016) on April 2, 2016 in Eindhoven, The Netherlands. The workshop is an event of the European Joint Conferences on Theory and Practice of Software (ETAPS 2016). The aim of the VPT workshops is to provide a forum where people from the area of program transformation and the area of program verification can fruitfully exchange ideas and gain a deeper understanding of the interactions between those two fields. The research papers which have been recently published in those fields, show that the interactions are very beneficial and, indeed, go both ways. In one direction, methods and tools developed in the field of program transformation, such as partial deduction, partial evaluation, fold/unfold transformations, and supercompilation, have all been applied with success for the verification of systems, and in particular, the verification of infinite state and parameterized systems. In the other direction, methods developed in program verification, such as model checking, abstract interpretation, SAT and SMT solving, and automated theorem proving, have been used to enhance program transformation techniques, thereby making these techniques more powerful and useful in practice.

Both automatic program verification and program transformation are based on program analysis. In the past decade a number of approaches using various automatic general-purpose program transformation techniques (partial deduction, specialization, supercompilation) for verification of unreachability properties of computing systems were introduced and demonstrated. On the other hand, the semantics based unfold-fold program transformation methods pose themselves diverse kinds of reachability tasks and try to solve them, aiming at improving the semantics tree of the program being transformed. That means some general-purpose verification methods may be used for strengthening program transformation techniques. This paper considers the question how finite countermodels for safety verification method might be used in Turchin's supercompilation method. We extract a number of supercompilation sub-algorithms trying to solve reachability problems and demonstrate use of an external countermodel finder for solving some of the problems., Comment: In Proceedings VPT 2015, arXiv:1512.02215

This volume contains the papers selected among those which were presented at the 3rd International Workshop on Verification and Program Transformation (VPT 2015) held in London, UK, on April 11th, 2015. Previous editions of the Workshop were held at Saint-Petersburg (Russia) in 2013, and Vienna (Austria) in 2014. Those papers show that methods and tools developed in the field of program transformation such as partial evaluation and fold/unfold transformations, and supercompilation, can be applied in the verification of software systems. They also show how some program verification methods, such as model checking techniques, abstract interpretation, SAT and SMT solving, and automated theorem proving, can be used to enhance program transformation techniques, thereby making these techniques more powerful and useful in practice.

This is a report on our ongoing research on a combinatorial approach to knot recognition, using coloring of knots by certain algebraic objects called quandles. The aim of the paper is to summarize the mathematical theory of knot coloring in a compact, accessible manner, and to show how to use it for computational purposes. In particular, we address how to determine colorability of a knot, and propose to use SAT solving to search for colorings. The computational complexity of the problem, both in theory and in our implementation, is discussed. In the last part, we explain how coloring can be utilized in knot recognition.

We explore the application of automated reasoning techniques to unknot detection, a classical problem of computational topology. We adopt a two-pronged experimental approach, using a theorem prover to try to establish a positive result (i.e. that a knot is the unknot), whilst simultaneously using a model finder to try to establish a negative result (i.e. that the knot is not the unknot). The theorem proving approach utilises equational reasoning, whilst the model finder searches for a minimal size counter-model. We present and compare experimental data using the involutary quandle of the knot, as well as comparing with alternative approaches, highlighting instances of interest. Furthermore, we present theoretical connections of the minimal countermodels obtained with existing knot invariants, for all prime knots of up to 10 crossings: this may be useful for developing advanced search strategies., Comment: To appear in Proceedings of CICM 2014

In 1930s Paul Erdos conjectured that for any positive integer $C$ in any infinite $\pm 1$ sequence $(x_n)$ there exists a subsequence $x_d, x_{2d}, x_{3d},\dots, x_{kd}$, for some positive integers $k$ and $d$, such that $\mid \sum_{i=1}^k x_{i\cdot d} \mid >C$. The conjecture has been referred to as one of the major open problems in combinatorial number theory and discrepancy theory. For the particular case of $C=1$ a human proof of the conjecture exists; for $C=2$ a bespoke computer program had generated sequences of length $1124$ of discrepancy $2$, but the status of the conjecture remained open even for such a small bound. We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solvers, one can obtain a discrepancy $2$ sequence of length $1160$ and a proof of the Erd\H{o}s discrepancy conjecture for $C=2$, claiming that no discrepancy 2 sequence of length $1161$, or more, exists. In the similar way, we obtain a precise bound of $127\,645$ on the maximal lengths of both multiplicative and completely multiplicative sequences of discrepancy $3$. We also demonstrate that unrestricted discrepancy 3 sequences can be longer than $130\,000$., Comment: Revised and extended journal version of arXiv:1402.2184, http://arxiv.org/abs/1402.2184

In 1930s Paul Erdos conjectured that for any positive integer C in any infinite +1 -1 sequence (x_n) there exists a subsequence x_d, x_{2d}, ... , x_{kd} for some positive integers k and d, such that |x_d + x_{2d} + ... + x_{kd}|> C. The conjecture has been referred to as one of the major open problems in combinatorial number theory and discrepancy theory. For the particular case of C=1 a human proof of the conjecture exists; for C=2 a bespoke computer program had generated sequences of length 1124 having discrepancy 2, but the status of the conjecture remained open even for such a small bound. We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solvers, one can obtain a sequence of length 1160 with discrepancy 2 and a proof of the Erdos discrepancy conjecture for C=2, claiming that no sequence of length 1161 and discrepancy 2 exists. We also present our partial results for the case of C=3., Comment: 8 pages. The description of the automata is clarified

We present a verification methodology for analysing the decision-making component in agent-based hybrid systems. Traditionally hybrid automata have been used to both implement and verify such systems, but hybrid automata based modelling, programming and verification techniques scale poorly as the complexity of discrete decision-making increases making them unattractive in situations where complex logical reasoning is required. In the programming of complex systems it has, therefore, become common to separate out logical decision-making into a separate, discrete, component. However, verification techniques have failed to keep pace with this development. We are exploring agent-based logical components and have developed a model checking technique for such components which can then be composed with a separate analysis of the continuous part of the hybrid system. Among other things this allows program model checkers to be used to verify the actual implementation of the decision-making in hybrid autonomous systems., Comment: Submitted to Journal of Automated Software Engineering