Abstract We present an empirical study on the ability of Large Language Models (LLMs) to understand code by detecting semantically equivalent and inequivalent programs, that is, whether they compute the same result given the same input or not. To probe this, we deliberately perturb the program text by introducing semantics-preserving code transformations, namely copy propagation and constant folding. Using a benchmark of 11 Python functions with both equivalent and non-equivalent variants, we evaluate seven state-of-the-art LLMs (including ChatGPT, Claude, Gemini, and Deep-Seek) under zero-shot prompting, with and without minimal context. Despite strong performance in code generation tasks, the models often fail in this deeper reasoning challenge, misclassifying 41% of equivalent cases without context and 29% with context. Although prompting can improve performance, it does not address the underlying limitations of the models. We argue that improving LLMs themselves, through targeted fine-tuning, contrastive learning on equivalent and nonequivalent implementations, or training on transformation-invariant code, will be necessary for robust semantic understanding. Meanwhile, practitioners can achieve better results by selecting stronger models, carefully engineering prom-pts, or writing code with tools that normalize low-level differences before inference.

The efficient execution of data center jobs that require simultaneous use of different resource types is of critical importance. When processing capacity is the crucial resource for jobs execution, the locution multiserver jobs is used, where the term server indicates processors or CPU cores providing processing capacity. Each multiserver job carries a requirement expressed in number of servers it requires to run, and service duration. Achieving efficient execution of multiserver jobs relies heavily on effective scheduling of jobs on the existing servers. Several schedulers have been proposed, aimed at improving resource utilization, at the cost of increased complexity. Due to the limited availability of theoretical results on scheduler behavior in the case of multiserver jobs, data center schedulers are often designed based only on managers' experience. In this paper, aiming to expand the understanding of the multiserver job schedulers' performance, we study Small Shuffle (SMASH) schedulers, a class of nonpreemptive, service time oblivious, window-based multiserver job scheduling algorithms that strike a balance between simplicity and efficient resource utiliza tion, while allowing performance evaluation in simpler settings. SMASHimplies only a marginal increase in complexity compared to FIFO, yet it delivers substantial performance improvements for multiserver jobs. Depending on the system parameters, SMASH can nearly double the system's stability region with respect to FIFO, leading to significantly lower response times across a broad region of loads. Moreover, the magnitude of this improvement scales with the chosen window size, allowing performance to be tuned to the system's operating conditions. We first study the capacity of SMASH with analytical tools in simple settings, then we investigate the performance of SMASH and other schedulers with simulations under more realistic workloads, designed with parameters derived from measurements of real data centers. Results show that SMASH offers a very good compromise between performance and complexity.

Smart contracts have played a pivotal role in the evolution of blockchains and Decentralized Applications (DApps). As DApps continue to gain widespread adoption, multiple smart contract languages have been and are being made available to developers, each with its distinctive features, strengths, and weaknesses. In this paper, we examine the smart contract languages used in major blockchain platforms, with the goal of providing a comprehensive assessment of their main properties. Our analysis targets the programming languages rather than the underlying architecture: as a result, while we do consider the interplay between language design and blockchain model, our main focus remains on language-specific features such as usability, programming style, safety and security. To conduct our assessment, we propose an original benchmark which encompasses a wide, yet manageable, spectrum of key use cases that cut across all the smart contract languages under examination. • We give an abstract overview of smart contract platforms, discussing the impact of different design choices. • We illustrate by examples how different design choices give rise to different programming styles for smart contracts. • We consider 6 leading smart contract languages: Solidity (Ethereum), Rust (Solana), Aiken (Cardano), PyTeal (Algorand), Move (Aptos), SmartPy (Tezos). • We develop an open-source benchmark of use cases of smart contracts, implemented in all the languages in our selection. • Based on our benchmark, we evaluate smart contract languages focussing on their security, code readability, usability, and functionalities.

The theory of noninterference supports the analysis of information leakage and the execution of secure computations in multi-level security systems. Classical equivalence-based approaches to noninterference mainly rely on weak bisimulation semantics. We show that this approach is not sufficient to identify potential covert channels in the presence of reversible computations. As illustrated via a database management system example, the activation of backward computations may trigger information flows that are not observable when proceeding in the standard forward direction. To capture the effects of back-and-forth computations, it is necessary to switch to a more expressive semantics, which has been proven to be branching bisimilarity in a previous work by De Nicola, Montanari, and Vaandrager. In this paper we investigate a taxonomy of noninterference properties based on branching bisimilarity along with their preservation and compositionality features, then we compare it with the taxonomy of Focardi and Gorrieri based on weak bisimilarity.

Blockchain technology has experienced significant advancements, with Proof-of-Stake emerging as a notable alternative to traditional Proof-of-Work blockchains. Among various PoS blockchain systems, Cosmos stands out as a prominent example due to its ecosystem designed to facilitate interoperability between different blockchains built on their platform through the Inter-Blockchain Communication protocol. What is more, Cosmos is operated by the unique consensus mechanism, namely CosmosBFT that supports multiple rounds for an agreement on block of the same height. This study examines the current state of blockchains within the Cosmos ecosystem, highlighting two major issues. First, we observe the multi-round performance in Cosmos blockchain using the process algebra tool to create our model featured non-homogeneous proposers. Second, we propose a method for determining optimal timeouts for the Propose step in any network within the ecosystem. In addition, we identify a skewed distribution of voting power among validators, favouring top-ranked members. This concentration of VP threatens the network’s decentralisation and immutability, as it allows a small group of members to potentially corrupt the consensus process. Our models, although parameterised for a particular Cosmos instance, are applicable to any blockchain that use the CometBFT protocol, offering valuable insights for enhancing efficiency of consensus mechanisms in the decentralised networks.

Advancements in Neural Networks have led to larger models, challenging implementation on embedded devices with memory, battery, and computational constraints. Consequently, network compression has flourished, offering solutions to reduce operations and parameters. However, many methods rely on heuristics, often requiring re-training for accuracy. Model reduction techniques extend beyond Neural Networks, relevant in Verification and Performance Evaluation fields. This paper bridges widely-used reduction strategies with formal concepts like lumpability, designed for analyzing Markov Chains. We propose a pruning approach based on lumpability, preserving exact behavioral outcomes without data dependence or fine-tuning. Relaxing strict quotienting method definitions enables a formal understanding of common reduction techniques.

Abstract Reversibility is the capability of a system of undoing its own actions starting from the last performed one, in such a way that a past consistent state is reached. This is not trivial for concurrent systems, as the last performed action may not be uniquely identifiable. There are several approaches to address causality-consistent reversibility, some including a notion of forward-reverse bisimilarity. We introduce a minimal process calculus for reversible systems to investigate compositionality properties and equational characterizations of forward-reverse bisimilarity as well as of its two components, i.e., forward bisimilarity and reverse bisimilarity, so as to highlight their differences. The study is conducted not only in a nondeterministic setting, but also in a stochastic one where time reversibility and lumpability for Markov chains are exploited.

In blockchain networks driven by Proof of Work, clients spend a certain amount of cryptocurrency (called fees) to control the speed of confirmation of the transactions that they generate. In fact, transactions are confirmed according to a strong priority policy that favours those offering the highest fees. The problem of determining the optimal fee to offer to satisfy certain delay requirements is still widely open and, at the state of the art, mainly reactive methods based on historical data are available. In this work, we propose a queueing model based on the exact transient analysis of a M/MB/1 system to address this problem. The model takes into account (i) the state of the Mempool (the backlog of pending work) when the transaction is generated, (ii) the current transaction arrival intensity and (iii) the distribution of the fees offered by other transactions to the miners. We apply the model to study the performance of the Bitcoin blockchain. Its parameterisation is based on an extensive statistical analysis of the transaction characteristics. To this aim, we collected data from over 1.5 million of pending transactions observed in the Mempool of our Bitcoin node. The outcome of our analysis allows us to provide an algorithm to quickly compute the expected transaction confirmation time given the blockchain state, and to highlight new insights on the relations between the transaction fees and confirmation time in BTC blockchain.

Abstract In this paper, we deal with the lumpability approach to cope with the state space explosion problem inherent to the computation of the stationary performance indices of large stochastic models. The lumpability method is based on a state aggregation technique and applies to Markov chains exhibiting some structural regularity. Moreover, it allows one to efficiently compute the exact values of the stationary performance indices when the model is actually lumpable. The notion of quasi-lumpability is based on the idea that a Markov chain can be altered by relatively small perturbations of the transition rates in such a way that the new resulting Markov chain is lumpable. In this case, only upper and lower bounds on the performance indices can be derived. Here, we introduce a novel notion of quasi-lumpability, named proportional lumpability, which extends the original definition of lumpability but, differently from the general definition of quasi-lumpability, it allows one to derive exact stationary performance indices for the original process. We then introduce the notion of proportional bisimilarity for the terms of the performance process algebra PEPA. Proportional bisimilarity induces a proportional lumpability on the underlying continuous-time Markov chains. Finally, we prove some compositionality results and show the applicability of our theory through examples.

In this paper, we study an information flow security property for systems specified as terms of a quantitative Markovian process algebra, namely the Performance Evaluation Process Algebra (PEPA). We propose a quantitative extension of the Non-Interference property used to secure systems from the functional point view by assuming that the observers are able to measure also the timing properties of the system, e.g., the response time of certain actions or its throughput. We introduce the notion of Persistent Stochastic Non-Interference (PSNI) based on the idea that every state reachable by a process satisfies a basic Stochastic Non-Interference (SNI) property. The structural operational semantics of PEPA allows us to give two characterizations of PSNI: one based on a bisimulation-like equivalence relation inducing a lumping on the underlying Markov chain, and another one based on unwinding conditions which demand properties of individual actions. These two different characterizations naturally lead to efficient methods for the verification and construction of secure systems. A decision algorithm for PSNI is presented and an application of PSNI to a queueing system is discussed.

Size-based scheduling policies have been widely studied in the literature, and their interest in networking applications has been huge in the last decade. These policies consist in deciding the priority of the packets belonging to a certain flow based on the service time that the flow has received up to a certain epoch or, when possible, on the remaining service time. The scientific literature has devoted many efforts to the comparison and analysis of these disciplines either by simulation or by analytical models although real-world implementations can have different performance for numerous reasons. In this paper, we consider the two-level processor sharing discipline (2LPS), i.e., packets are served with high priority if they belong to a flow that has required less than a work up to that moment, where a is a threshold-parameter of the model. The goal is that of assessing the performance of this discipline once implemented in a real router with a real-world network traffic and compare these measurements with the performance indices obtained by the queueing model. To characterise the networks traffic, we fit two datasets with an acyclic phase-type distribution thanks to an existing tool and then transform the resulting distribution into a generalised hypergeometric distribution. Our experiments confirm that the 2LPS improves the flow expected response time with respect to the standard scheduling by taking advantage of the heavily tailed distribution characterising the TCP flow sizes, but this improvement seems slightly smaller than what predicted by the analytical models.

We consider the scenario in which several TCP connections share the same access point (AP) and a congestion avoidance/control mechanism is adopted with the aim of assigning the available bandwidth to the clients with a certain fairness. When UDP traffic with real-time requirements is present, the problem becomes even more challenging. Very well-known congestion avoidance mechanisms are the Random Early Detection (RED) and the Explicit Congestion Notification (ECN). More recently, the Smart Access Point with Limited Advertised Window (SAP-LAW) has been proposed. Its main idea is that of computing the maximum TCP rate for each connection at the bottleneck, taking into account the UDP traffic to keep a low queue size combined with a reasonable bandwidth utilization. In this paper, we propose a new congestion control mechanism, namely, Smart-RED, inspired by SAP-LAW heuristic formula. We study its performance by using mean field models and compare the behaviours of ECN/RED, SAP-LAW, and Smart-RED under different scenarios. We show that while Smart-RED maintains some of the desirable properties of the SAP-LAW, it solves the problems it may have in case of bursty UDP traffic or TCP connections with very different needs of bandwidth.

Active Queue Management (AQM) techniques have been proposed to support scenarios with many connections sharing the same bottleneck. The basic idea is that a smart management of the bottleneck queue can avoid the saturation of the link and ensure a smoother use of the available bandwidth. This is generally achieved by exploiting the flux control mechanism of TCP and its behavior in case of packet losses or other explicit notifications. In this paper we consider classic and innovative AQM techniques and analyse their performance under different scenarios through the use of mean field models.

Probabilistic I/O automata (PIOAs) provide a modelling framework that is well suited for describing and analyzing distributed and concurrent systems. They incorporate a notion of probabilistic choice as well as a notion of composition that allows one to construct a PIOA for a composite system from a collection of simpler PIOAs representing the components. Differently from other probabilistic models, the local actions of a PIOA are associated with time delays governed by independent random variables with continuous-time exponential distributions. The contribution of this paper consists in studying the product-form property for PIOAs. Our main result is the formulation of a theorem giving sufficient conditions for a composition of PIOAs to be in product-form and hence to efficiently compute its stationary probabilities.

In this paper we propose a new model for the analysis of systems with aging objects such as Time-To-Live cache. We consider a model with an underlying Continuous Time Markov Chain in which objects can be completely or partially rejuvenated. In the former case the object becomes fresh, while in the latter all the objects are simultaneously rejuvenated so that the youngest becomes fresh. We show that under the so-called Independent Reference Model assumption our model is numerically tractable and has a product-form equilibrium distribution. Furthermore, we consider the case in which the object aging stops after a certain threshold and hence the partial rejuvenation introduces a probabilistic behaviour. Also in this case, we can derive a product-form equilibrium distribution under some mild conditions. The models presented in this paper may be interpreted as a new class of G-networks with catastrophes and partial flushing.

In the literature devoted to the efficient solution of Continuous Time Markov Chains (CTMCs) the notions of lump ability and reversibility have a central role. In the context of lump able Markov chains several definitions have been introduced: strong, exact and strict, just to mention a few of them. On the side of the analysis of reversible CTMCs the research community has shown great interest in the application of this notion with the aim of efficiently computing the stationary distribution of large models (e.g., obtained by composition of several processes). In this paper we show for the first time the relations between the above mentioned notions of lump ability and the concept of reversibility. The major outcome of our research is proving a strong connection between the notion of strict lump ability and that of reversibility.

The computation of the steady-state distribution of Continuous Time Markov Chains (CTMCs) may be a computationally hard problem when the number of states is very large. In order to overcome this problem, in the literature, several solutions have been proposed such as the reduction of the state space cardinality by lumping, the factorization based on product-form analysis and the application of the notion of reversibility. In this paper we address this problem by introducing the notion of auto reversibility which is defined as a symmetric co inductive relation which induces an equivalence relation among the chain's states. We show that all the states belonging to the same equivalence class share the same stationary probabilities and hence the computation of the steady-state distribution can be computationally more efficient. The definition of auto reversibility takes inspiration by the Kolmogorov's criteria for reversible processes and hence requires to test a property on all the minimal cycles of the chain. We show that the notion of auto reversibility is different from that of reversible processes and does not correspond to other state aggregation techniques such as lumping. Finally, we discuss the applicability of our results in the case of models defined in terms of a Markovian process Algebra such as the Performance Evaluation Process Algebra.

We present a framework for modelling ad-hoc Wireless Sensor Networks (WSNs) and studying both their connectivity properties and their performances in terms of energy consumption, throughput and other relevant indices. Our framework is based on a probabilistic process calculus where system executions are driven by Markovian probabilistic schedulers, allowing us to translate process terms into discrete time Markov chains (DTMCs) and use the probabilistic model checker PRISM to automatically evaluate/estimate the connectivity properties and the energy costs of the networks. To the best of our knowledge, this is the first work that proposes a unique framework for studying qualitative (e.g., by proving the equivalence of components or the correctness of a behaviour) and quantitative aspects of WSNs using a tool that allows both exact and approximate (via Monte Carlo simulation) analyses. We demonstrate our framework at work by considering different communication strategies based on gossip routing protocols, for a typical topology and a mobility scenario.

ABSTRACT Energy conservation is a critical issue in mobile ad hoc networks (MANETs) for both nodes and network lifetime, as only batteries power nodes. In this paper, we present the E‐BUM calculus, an Energy‐aware calculus for Broadcast, Unicast and Multicast communications of MANETs. In order to reason about cost‐effective ad hoc routing protocols, our calculus captures the possibility for a node to control the transmission radius of its communications. We show how to use the E‐BUM calculus in order to prove some useful connectivity properties of MANETs, to control network topology and to reason about the problem of reducing interference. In particular, we formalize the notions of sender‐centred and receiver‐centred interference and provide efficient proof techniques for verifying the absence of interference between a specific set of nodes. Copyright © 2012 John Wiley & Sons, Ltd.

Mobile ad-hoc and sensor networks play an important role in several application fields. The usage of wireless links and the node mobility make the networks prone to security attacks; among these, jamming attacks are insidious and they consist of one or more nodes continuously transmitting dummy packets to keep some wireless links busy. The goal is to destroy the network connectivity or highly reduce its throughput. In this paper we propose a probabilistic formal method, based on a process algebraic approach, targeted at the analysis of connectivity and the evaluation of interference in mobile networks. We show our framework at work on the analysis of an indoor wireless communication scenario.

We present a general unwinding framework for the definition of information flow security properties of concurrent programs, described in a simple imperative language enriched with parallelism and atomic statement constructors. We study different classes of programs obtained by instantiating the general framework and we prove that they entail the noninterference principle. Accurate proof techniques for the verification of such properties are defined by exploiting the Tarski decidability result for first-order formulae over the reals. Moreover, we illustrate how the unwinding framework can be instantiated in order to deal with intentional information release and we extend our verification techniques to the analysis of security properties of programs admitting downgrading.

We study information flow security in the setting of mobile agents. We propose a sufficient condition to security named Persistent_BNDC. A process is Persistent_BNDC when every of its reachable states satisfies a basic Non-Interference property called BNDC. By imposing that security persists during process execution, one is guaranteed that every potential migration is performed in a stable, secure state. We define a suitable bisimulation-based equivalence relation among processes, that allows us to express the new property as a single equivalence check, thus avoiding the universal quantifications over all the reachable states (required by Persistent_BNDC) and over all the possible hostile environments (implicit in the basic Non-Interference property BNDC). We prove that Persistent_BNDC is a sufficient condition to the security of mobile agents by (i) giving a sound and complete characterization of Persistent_BNDC in terms of dynamic contexts, i.e., execution contexts that can non-deterministically change at run-time, abstractly modelling arbitrary migrations; (ii) showing that Persistent_BNDC implies information flow security when agent mobility is explicitly expressed in the calculus.

Information flow security in a multilevel system aims at guaranteeing that no high level information is revealed to low level users, even in the presence of any possible malicious process. This requirement could be stronger than necessary when some knowledge about the environment (context) in which the process is going to run is available. To relax this requirement we introduce the notion of secure contexts for a class of processes. This notion is parametric with respect to both the observation equivalence and the operation used to characterize the low level view of a process. As observation equivalence we consider the cases of weak bisimulation and trace equivalence. We describe how to build secure contexts in these cases and we show that two well-known security properties, named BNDC and NDC, are just special instances of our general notion.

Non-interference has been advocated by various authors as a uniform framework for the formal specification of security properties in cryptographic protocols. Unfortunately, specifications based on non-interference are often non-effective, as they req

In logic programming,dynamic schedulingindicates the feature by means of which the choice of the atom to be selected at each resolution step is done at runtime and does not follow a fixed selection rule such as the left-to-right one of Prolog.Input-consuming derivationswere introduced to model dynamic scheduling while abstracting from the technical details. In this article, we provide a sufficient and necessary criterion for termination of input-consuming derivations of simply moded logic programs. The termination criterion we propose is based on a denotational semantics for partial derivations which is defined in the spirit of model-theoretic semantics previously proposed for left-to-right derivations.

Information flow security in a multilevel system aims at guaranteeing that no high level information is revealed to low level users, even in the presence of any possible malicious process. This requirement could be too demanding when some knowledge about the environment (context) in which the process is going to run is available. To deal with these simulations we introduce the notion of secure contexts for a class of processes. This notion is parametric with respect to both the observation equivalence and the operation used to characterize the low level behavior of a process. We mainly analyze the cases of bisimulation and trace equivalence. We describe how to build secure contexts in these cases and we show that two well-known security properties, named BNDC and NDC, are just special instances of our general notion.

The systematic development of complex systems usually relies on a stepwise refinement procedure from an abstract specification to a more concrete one that can finally be implemented. The use of refinement operators preserving system properties is clearly essential since it avoids properties to be re-investigated at each development step. In this paper, we formalize the notion of refinement for processes described as terms of the security process algebra (SPA). We consider several information flow security properties and provide sufficient conditions under which our refinement operators preserve such security properties. Finally, we study how refinements can be composed still preserving the security of the system.

We propose a modular method for proving termination of general logic programs (i.e. logic programs with negation). It is based on the notion of acceptable programs, but it allows us to prove termination in a truly modular way. We consider programs consisting of a hierarchy of modules and supply a general result for proving termination by dealing with each module separately. For programs which are in a certain sense well-behaved, namely well-moded or well-typed programs, we derive both a simple verification technique and an iterative proof method. Some examples show how our system allows for greatly simplified proofs.

We study the properties of input-consuming derivations of moded logic programs. Input-consuming derivations can be used to model the behavior of logic programs using dynamic scheduling and employing constructs such as delay declarations. We consider the class of nicely-moded programs and queries. We show that for these programs a weak version of the well-known switching lemma holds also for input-consuming derivations. Furthermore, we show that, under suitable conditions, there exists an algebraic characterization of termination of input-consuming derivations.

Abstract interpretation is a general methodology for systematic development of program analyses. An abstract interpretation framework is centered around a parametrized non-standard semantics that can be instantiated by various domains to approximate different program properties. Many abstract interpretation frameworks and analyses for Prolog have been proposed, which seek to extract information useful for program optimization. Although motivated by practical considerations, notably making Prolog competitive with imperative languages, such frameworks fail to capture some of the control structures of existing implementations of the language. In this paper, we propose a novel framework for the abstract interpretation of Prolog which handles the depth-first search rule and the cut operator. It relies on the notion of substitution sequence to model the result of the execution of a goal. The framework consists of (i) a denotational concrete semantics, (ii) a safe abstraction of the concrete semantics defined in terms of a class of post-fixpoints, and (iii) a generic abstract interpretation algorithm. We show that traditional abstract domains of substitutions may easily be adapted to the new framework, and provide experimental evidence of the effectiveness of our approach. We also show that previous work on determinacy analysis, that was not expressible by existing abstract interpretation frameworks, can be seen as an instance of our framework. The ideas developed in this paper can be applied to other logic languages, notably to constraint logic languages, and the theoretical approach should be of general interest for the analysis of many non-deterministic programming languages.

We consider an extended definition of well-typed programs to general logic programs, i.e. logic programs with negated literals in the body of the clauses. This is a quite large class of programs which properly includes all the well-moded ones. We study termination properties of well-typed general programs while employing the Prolog's left-to-right selection rule. We introduce the notion of typed acceptable program and provide an algebraic characterization for the class of well-typed programs whic hterminate on all well-typed queries.