Antibiotic resistance poses a global health issue that requires innovative techniques for predicting antibiotic resistance genes (ARGs). Traditionally, prediction models depended on sequence-based methods that examined protein sequences to detect ARGs. However, these approaches frequently encounter challenges in identifying the connections between proteins and their interactions. To address this problem, we introduce GNN-ARG, a framework that investigates graph neural network (GNN) architectures to predict ARG from protein sequences using protein interaction graphs. Our method builds a weighted, undirected graph where nodes correspond to proteins and links indicate how similar they are. We utilize existing ESM-2 embeddings as features for nodes to capture specific sequence details. For training GNN-ARG, we employed a dataset combining protein sequences categorized as either ARG or non-ARG from nine public ARG databases. The model was trained with the aim of predicting node labels through binary classification tasks. In the GNN-ARG framework, we conducted a thorough assessment of four well-known GNN models: Graph Convolutional Networks (GCN), Graph Isomorphism Networks (GIN), Graph Attention Networks (GAT), and Graph Sage. Our experimental findings show that GIN outperforms the others providing an accuracy of 93.22% with an F1 score of 0.9161, followed by GCN and Graph Sage, which also show performance closely behind GIN. Despite providing insights into node importance, the GAT model achieves both lower accuracy and F1 score. These results highlight how GNN models can improve the prediction of resistance genes and help us gain a deeper understanding of ways to address antibiotic resistance more effectively in the future research field of bioinformatics by exploring graph-based methods extensively.

In the next few years, applications of Generative AI are expected to revolutionize a number of different areas, ranging from science & medicine to education. The potential for these seismic changes has triggered a lively debate about potential risks and resulted in calls for tighter regulation, in particular from some of the major tech companies who are leading in AI development. While regulation is important, it is key that it does not put at risk the budding field of open-source Generative AI. We argue for the responsible open sourcing of generative AI models in the near and medium term. To set the stage, we first introduce an AI openness taxonomy system and apply it to 40 current large language models. We then outline differential benefits and risks of open versus closed source AI and present potential risk mitigation, ranging from best practices to calls for technical and scientific contributions. We hope that this report will add a much needed missing voice to the current public discourse on near to mid-term AI safety and other societal impact.

Identifying out-of-distribution (OOD) data at inference time is crucial for many machine learning applications, especially for automation. We present a novel unsupervised semi-parametric framework COMBOOD for OOD detection with respect to image recognition. Our framework combines signals from two distance metrics, nearest-neighbor and Mahalanobis, to derive a confidence score for an inference point to be out-of-distribution. The former provides a non-parametric approach to OOD detection. The latter provides a parametric, simple, yet effective method for detecting OOD data points, especially, in the far OOD scenario, where the inference point is far apart from the training data set in the embedding space. However, its performance is not satisfactory in the near OOD scenarios that arise in practical situations. Our COMBOOD framework combines the two signals in a semi-parametric setting to provide a confidence score that is accurate both for the near-OOD and far-OOD scenarios. We show experimental results with the COMBOOD framework for different types of feature extraction strategies. We demonstrate experimentally that COMBOOD outperforms state-of-the-art OOD detection methods on the OpenOOD (both version 1 and most recent version 1.5) benchmark datasets (for both far-OOD and near-OOD) as well as on the documents dataset in terms of accuracy.

Abstract UML sequence diagrams are visual representations of object interactions in a system and can provide valuable information for program comprehension, debugging, maintenance, and software archeology. Sequence diagrams generated from legacy code are independent of existing documentation that may have eroded. We present a framework for static generation of UML sequence diagrams from object-oriented source code. The framework provides a query refinement system to guide the user to interesting interactions in the source code. Our technique involves constructing a hypergraph representation of the source code, traversing the hypergraph with respect to a user-defined query, and generating the corresponding set of sequence diagrams. We implemented our framework as a tool, StaticGen (supporting software: StaticGen ), analyzing a corpus of 30 Android applications. We provide experimental results demonstrating the efficacy of our technique (originally appeared in the Proceedings of Fundamental Approaches to Software Engineering—20th International Conference, FASE 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017).

We present OptEx, a closed-form model of job execution on Apache Spark, a popular parallel processing engine. To the best of our knowledge, OptEx is the first work that analytically models job completion time on Spark. The model can be used to estimate the completion time of a given Spark job on a cloud, with respect to the size of the input dataset, the number of iterations, and the number of nodes comprising the underlying cluster. Experimental results demonstrate that OptEx yields a mean relative error of 6 percent in estimating the job completion time. Furthermore, the model can be applied for estimating the cost-optimal cluster composition for running a given Spark job on a cloud under a completion deadline specified in theSLO(i.e., Service Level Objective). We show experimentally that OptEx is able to correctly estimate the required cluster composition for running a given Spark job under a given SLO deadline with an accuracy of 98 percent. We also provide a tool which can classify Spark jobs into job categories based on bisimilarity analysis on lineage graphs collected from the given jobs.

Recent work in deep neural networks has sought to characterize the nature in which a network learns features and how applicable learnt features are to various problem sets. Deep neural network applicability can be split into three sub-problems; set applicability, class applicability, and instance applicability. In this work we seek to quantify the applicability of features learned during adversarial training, focusing specifically on set and class applicability. We apply techniques for measuring applicability to both generators and discriminators trained on various data sets to quantify applicability.

Building performance discrepancies between building design and operation are one of the causes that lead many new designs fail to achieve their goals and objectives. A main factor contributing to the discrepancy is occupant behaviors. Occupants responding to a new design are influenced by several factors. Existing building performance models (BPMs) ignore or partially address those factors (called contextual factors) while developing BPMs. To potentially reduce the discrepancies and improve the prediction accuracy of BPMs, this paper proposes a computational framework for learning mixture models by using Generative Adversarial Networks (GANs) that appropriately combining existing BPMs with knowledge on occupant behaviors to contextual factors in new designs. Immersive virtual environments (IVEs) experiments are used to acquire data on such behaviors. Performance targets are used to guide appropriate combination of existing BPMs with knowledge on occupant behaviors. The resulting model obtained is called an augmented BPM. Two different experiments related to occupants lighting behaviors are shown as case study. The results reveal that augmented BPMs significantly outperformed existing BPMs with respect to achieving specified performance targets. The case study confirmed the potential of the computational framework for improving prediction accuracy of BPMs during design.

Route Choice Models predict the route choices of travelers traversing an urban area. Most of the route choice models link route characteristics of alternative routes to those chosen by the drivers. The models play an important role in prediction of traffic levels on different routes and thus assist in development of efficient traffic management strategies that result in minimizing traffic delay and maximizing effective utilization of transport system. High fidelity route choice models are required to predict traffic levels with higher accuracy. Existing route choice models do not take into account dynamic contextual conditions such as the occurrence of an accident, the socio-cultural and economic background of drivers, other human behaviors, the dynamic personal risk level, etc. As a result, they can only make predictions at an aggregate level and for a fixed set of contextual factors. For higher fidelity, it is highly desirable to use a model that captures significance of subjective or contextual factors in route choice. This paper presents a novel approach for developing high-fidelity route choice models with increased predictive power by augmenting existing aggregate level baseline models with information on drivers' responses to contextual factors obtained from Stated Choice Experiments carried out in an Immersive Virtual Environment through the use of knowledge distillation.

We demonstrate Dyn-YCSB, a tool that builds upon YCSB (Yahoo Cloud Serving Benchmark suite) to assist users in simulating dynamic variations in workloads. Dyn-YCSB automatically varies the parameters in YCSB workloads over time according to user-specified time series functions, without requiring users to manually change the workload configuration in individual nodes each time the workload parameters needs to be modified. The dynamic workload variations simulated with Dyn-YCSB can be used to evaluate the adaptability of such frameworks to changing workload characteristics. We demonstrate the ability of Dyn-YCSB to evaluate the adaptability of OptCon, an automated framework, that tunes the consistency settings of Cassandra with respect to the latency and staleness thresholds in an SLA.

Classification techniques for images of handwritten characters are susceptible to noise. Quadtrees can be an efficient representation for learning from sparse features. In this paper, we improve the effectiveness of probabilistic quadtrees by using a pixel level classifier to extract the character pixels and remove noise from handwritten character images. The pixel level denoiser (a deep belief network) uses the map responses obtained from a pretrained CNN as features for reconstructing the characters eliminating noise. We experimentally demonstrate the effectiveness of our approach by reconstructing and classifying a noisy version of handwritten Bangla Numeral and Basic Character datasets.

The coordination problems arising in a team of autonomous mobile robots have received a lot of attention in the distributed robotics community. Along those lines, we study in this paper the problem of coordinating autonomous mobile robots to reposition on a convex hull so that each robot sees all others. In particular, we consider non-transparent fat robots operating in the 2-dimensional plane. They are abstracted as unit discs and they make local decisions with vision being the only mean of coordination among them. We develop a (deterministic) distributed algorithm that solves the problem for a team of N ≥ 3 fat robots in O(N) time avoiding collisions under the semi-synchronous scheduler. The main idea is to enforce the robots to reach a configuration in which (i) the robots' centers form a convex hull; (ii) all robots are on the convex hull's boundary; and (iii) each robot can see all other robots. The result is achieved assuming some reasonable conditions on the input configuration and showing that starting from any input configuration that satisfies our conditions, robots reach such a configuration in linear time and terminate.

Deep neural networks trained over large datasets learn features that are both generic to the whole dataset, and specific to individual classes in the dataset. Learned features tend towards generic in the lower layers and specific in the higher layers of a network. Methods like fine-tuning are made possible because of the ability for one filter to apply to multiple target classes. Much like the human brain this behavior, can also be used to cluster and separate classes. However, to the best of our knowledge there is no metric for how applicable learned features are to specific classes. In this paper we propose a definition and metric for measuring the applicability of learned features to individual classes, and use this applicability metric to estimate input applicability and produce a new method of unsupervised learning we call the CactusNet.

Deep Convolutional features extracted from a comprehensive labeled dataset, contain substantial representations which could be effectively used in a new domain. Despite the fact that generic features achieved good results in many visual tasks, fine-tuning is required for pretrained deep CNN models to be more effective and provide state-of-the-art performance. Fine tuning using the backpropagation algorithm in a supervised setting, is a time and resource consuming process. In this paper, we present a new architecture and an approach for unsupervised object recognition that addresses the above mentioned problem with fine tuning associated with pretrained CNN-based supervised deep learning approaches while allowing automated feature extraction. Unlike existing works, our approach is applicable to general object recognition tasks. It uses a pretrained (on a related domain) CNN model for automated feature extraction pipelined with a Hopfield network based associative memory bank for storing patterns for classification purposes. The use of associative memory bank in our framework allows eliminating backpropagation while providing competitive performance on an unseen dataset.

We consider the distributed setting of $N$ autonomous mobile robots that operate in Look-Compute-Move cycles following the well-celebrated classic oblivious robots model. We study the fundamental problem where starting from an arbitrary initial configuration, N autonomous robots reposition themselves to a convex hull formation on the plane where each robot is visible to all others (the Complete Visibility problem). We assume obstructed visibility, where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We provide the first \cO(N) time algorithm for this problem in the fully synchronous setting. Our contribution is a significant improvement over the runtime of the only previously known algorithm for this problem which has a lower bound of \Omega(N^2). Our proposed algorithm is collision-free -- robots do not share positions and their paths do not cross.

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane that have a physical extent and hence cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem with minimum time objective has applications in many real-world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (in Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, 2011) gave a local greedy algorithm in a fully synchronous setting and proved that, for the discrete version of the problem where robots’ movements are restricted to the positions on an integral grid, their algorithm solves this problem in O ( nR ) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this article, we improve significantly the round complexity of their algorithm to R + 2 · ( n - 1) rounds. This round complexity is obtained in the following modified model: (1) the viewing range of the robots is increased to three hops and (2) robots can additionally move to the diagonally opposite corner to a grid cell in one step—that is, they can traverse the two corresponding grid edges in one time step. We also prove that there are initial configurations of n robots in this problem where at least R +(n-1)/2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + ( n - 1) rounds for the algorithm of Cord-Landwehr et al. These results altogether provide a tight runtime analysis of their algorithm.

Users of distributed datastores that employ quorum-based replication are burdened with the choice of a suitable client-centric consistency setting for each storage operation. The above matching choice is difficult to reason about as it requires deliberating about the tradeoff between the latency and staleness, i.e., how stale (old) the result is. The latency and staleness for a given operation depend on the client-centric consistency setting applied, as well as dynamic parameters such as the current workload and network condition. We present OptCon, a machine learning-based predictive framework, that can automate the choice of client-centric consistency setting under user-specified latency and staleness thresholds given in the service level agreement (SLA). Under a given SLA, OptCon predicts a client-centric consistency setting that is matching, i.e., it is weak enough to satisfy the latency threshold, while being strong enough to satisfy the staleness threshold. While manually tuned consistency settings remain fixed unless explicitly reconfigured, OptCon tunes consistency settings on a per-operation basis with respect to changing workload and network state. Using decision tree learning, OptCon yields 0.14 cross validation error in predicting matching consistency settings under latency and staleness thresholds given in the SLA. We demonstrate experimentally that OptCon is at least as effective as any manually chosen consistency settings in adapting to the SLA thresholds for different use cases. We also demonstrate that OptCon adapts to variations in workload, whereas a given manually chosen fixed consistency setting satisfies the SLA only for a characteristic workload.

We present OptEx, a closed-form model of job execution on Apache Spark, a popular parallel processing engine. To the best of our knowledge, OptEx is the first work that analytically models job completion time on Spark. The model can be used to estimate the completion time of a given Spark job on a cloud, with respect to the size of the input dataset, the number of iterations, the number of nodes comprising the underlying cluster. Experimental results demonstrate that OptEx yields a mean relative error of 6% in estimating the job completion time. Furthermore, the model can be applied for estimating the cost optimal cluster composition for running a given Spark job on a cloud under a completion deadline specified in the SLO (i.e.,Service Level Objective). We show experimentally that OptEx is able to correctly estimate the cost optimal cluster composition for running a given Spark job under an SLO deadline with an accuracy of 98%.

Users of distributed datastores that employquorum-based replication are burdened with the choice of asuitable client-centric consistency setting for each storage operation. The above matching choice is difficult to reason about asit requires deliberating about the tradeoff between the latencyand staleness, i.e., how stale (old) the result is. The latencyand staleness for a given operation depend on the client-centricconsistency setting applied, as well as dynamic parameters such asthe current workload and network condition. We present OptCon, a novel machine learning-based predictive framework, that canautomate the choice of client-centric consistency setting underuser-specified latency and staleness thresholds given in the servicelevel agreement (SLA). Under a given SLA, OptCon predictsa client-centric consistency setting that is matching, i.e., it isweak enough to satisfy the latency threshold, while being strongenough to satisfy the staleness threshold. While manually tunedconsistency settings remain fixed unless explicitly reconfigured, OptCon tunes consistency settings on a per-operation basis withrespect to changing workload and network state. Using decisiontree learning, OptCon yields 0.14 cross validation error in predictingmatching consistency settings under latency and stalenessthresholds given in the SLA. We demonstrate experimentally thatOptCon is at least as effective as any manually chosen consistencysettings in adapting to the SLA thresholds for different usecases. We also demonstrate that OptCon adapts to variationsin workload, whereas a given manually chosen fixed consistencysetting satisfies the SLA only for a characteristic workload.

Nowadays, the sufficient quality-of-service (QoS) provision for mobile applications remains a major challenge in any wireless network. Conventional sufficient QoS provision techniques using resource allocation, data scheduling, and cross-layer optimization have been proposed to tackle this problem. Nevertheless, due to the unpredictable nature of wireless channel conditions, the QoS improvements resulting from the aforementioned approaches are often unsatisfactory. In this paper, we would like to follow our previous concept, namely user-placement ushering (UPU), by use of the user's mobility. A mobile user can be relocated to an optimal, or at least a better place to boost the QoS for a particular application. Novel fast algorithms are devised here to usher (guide) the mobile user to an appropriate spot with sufficient QoS, which is nearby. We address the UPU problem to accommodate realistic complex indoor environments, where obstacles are present. Our simulation results have demonstrated that our new fast UPU algorithms are capable of finding new appropriate locations satisfying the required QoSs for different wireless network applications.

We investigate the use of Deep Neural Networks for the classification of image datasets where texture features are important for generating class-conditional discriminative representations. To this end, we first derive the size of the feature space for some standard textural features extracted from the input dataset and then use the theory of Vapnik-Chervonenkis dimension to show that hand-crafted feature extraction creates low-dimensional representations which help in reducing the overall excess error rate. As a corollary to this analysis, we derive for the first time upper bounds on the VC dimension of Convolutional Neural Network as well as Dropout and Dropconnect networks and the relation between excess error rate of Dropout and Dropconnect networks. The concept of intrinsic dimension is used to validate the intuition that texture-based datasets are inherently higher dimensional as compared to handwritten digits or other object recognition datasets and hence more difficult to be shattered by neural networks. We then derive the mean distance from the centroid to the nearest and farthest sampling points in an n-dimensional manifold and show that the Relative Contrast of the sample data vanishes as dimensionality of the underlying vector space tends to infinity.

Satellite image classification is a challenging problem that lies at the crossroads of remote sensing, computer vision, and machine learning. Due to the high variability inherent in satellite data, most of the current object classification approaches are not suitable for handling satellite datasets. The progress of satellite image analytics has also been inhibited by the lack of a single labeled high-resolution dataset with multiple class labels. The contributions of this paper are twofold -- (1) first, we present two new satellite datasets called SAT-4 and SAT-6, and (2) then, we propose a classification framework that extracts features from an input image, normalizes them and feeds the normalized feature vectors to a Deep Belief Network for classification. On the SAT-4 dataset, our best network produces a classification accuracy of 97.95% and outperforms three state-of-the-art object recognition algorithms, namely - Deep Belief Networks, Convolutional Neural Networks and Stacked Denoising Autoencoders by ~11%. On SAT-6, it produces a classification accuracy of 93.9% and outperforms the other algorithms by ~15%. Comparative studies with a Random Forest classifier show the advantage of an unsupervised learning approach over traditional supervised learning techniques. A statistical analysis based on Distribution Separability Criterion and Intrinsic Dimensionality Estimation substantiates the effectiveness of our approach in learning better representations for satellite imagery.

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane which have a physical extent and hence they cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem has applications in many real world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (SOFSEM 2011) gave a local greedy algorithm in a synchronous setting and proved that, for the discrete version of the problem where robots movements are restricted to the positions on an integral grid, their algorithm solves this problem in O(nR) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this paper, we improve significantly the round complexity of their algorithm to R + 2 · (n - 1) rounds. We also prove that there are initial configurations of n robots in this problem where at least R + (n - 1) over 2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + (n - 1) rounds for the algorithm of Cord-Landwehr et al.. These results altogether provide a tight runtime analysis of their algorithm.

Summary We present a formal framework for reasoning about security concerns in the context of embedded sensor networks. We first provide an agent‐based programming model for sensor networks. A logical framework enables reasoning about security, safety, and integrity with respect to usage of resources in this model. Embedded sensor networks often operate in rapidly changing mission‐critical environments where both functional and nonfunctional requirements can alter dynamically in an unforeseen manner. The network may need to be reconfigured and reprogrammed in response to changes in its operating conditions. We provide a framework based on counterfactual logic to formally represent changes to the system and perform what‐if reasoning about their impact on security and safety even before they have been applied. Copyright © 2015 John Wiley & Sons, Ltd.

Accurate tree-cover estimates are useful in deriving above-ground biomass density estimates from very high resolution (VHR) satellite imagery data. Numerous algorithms have been designed to perform tree-cover delineation in high-to-coarse-resolution satellite imagery, but most of them do not scale to terabytes of data, typical in these VHR data sets. In this paper, we present an automated probabilistic framework for the segmentation and classification of 1-m VHR data as obtained from the National Agriculture Imagery Program (NAIP) for deriving tree-cover estimates for the whole of Continental United States, using a high-performance computing architecture. The results from the classification and segmentation algorithms are then consolidated into a structured prediction framework using a discriminative undirected probabilistic graphical model based on conditional random field, which helps in capturing the higher order contextual dependence relations between neighboring pixels. Once the final probability maps are generated, the framework is updated and retrained by incorporating expert knowledge through the relabeling of misclassified image patches. This leads to a significant improvement in the true positive rates and reduction in false positive rates (FPRs). The tree-cover maps were generated for the state of California, which covers a total of 11 095 NAIP tiles and spans a total geographical area of 163 696 sq. miles. Our framework produced correct detection rates of around 88% for fragmented forests and 74% for urban tree-cover areas, with FPRs lower than 2% for both regions. Comparative studies with the National Land-Cover Data algorithm and the LiDAR high-resolution canopy height model showed the effectiveness of our algorithm for generating accurate high-resolution tree-cover maps.

This paper presents a semi-automated methodology for generating geometric proof problems of the kind found in a high-school curriculum. We formalize the notion of a geometry proof problem and describe an algorithm for generating such problems over a user-provided figure. Our experimental results indicate that our problem generation algorithm can effectively generate proof problems in elementary geometry. On a corpus of 110 figures taken from popular geometry textbooks, our system generated an average of about 443 problems per figure in an average time of 4.7 seconds per figure.

This paper tackles the low-density parity-check (LDPC) encoder identification problem encountered in the time-varying flat-fading channels which are modeled as finite-state Markov chains. The in-phase and quadrature-phase components of the channel coefficients are both represented by a number of states. To greatly simplify the computation of the channel observation probabilities, each channel-state region is further quantized to an interior point. Based on our proposed finite-state Markov model, the Viterbi algorithm is thus invoked to blindly estimate the unknown channel-state sequence from each received signal segment. To mitigate the phase ambiguity which is inherent in the channel-state estimation process, the pilot-aided channel estimation method is also proposed here. The LDPC encoder is finally identified in the framework of the log-likelihood ratio of syndrome a posteriori probability. The performance of our proposed LDPC identification scheme is investigated for different normalized Doppler rates and different mechanisms to reconstruct the channel-state information. Monte Carlo simulation results suggest that pilot symbols are necessary for leading to a satisfactory identification performance for time-varying flat-fading channels.

Formal verification of the trusted computing base of a software system is essential for its deployment in mission-critical environments. Commercial off-the-shelf routers are nowadays being used for managing traffic in high-assurance networks. The specifications for the development of these routers are provided by RFCs that are only described informally in English. It is essential to ensure that a router firmware conforms to its corresponding RFC before it can be deployed for managing mission-critical networks. In this paper, we report the formal verification of the conformance of the open source Netgear WNR3500L wireless router firmware implementation to the RFC 2131 [6] based on which it is designed. The formal verification effort led to the discovery of several possible problems in the implementation that we report in this paper. We have used the Coq proof assistant extensively in this verification effort. The formal verification process demonstrates the usefulness of inductive types and higher-order logic in software certification.

This article shows a novel program analysis framework based on Lewis' theory of counterfactuals. Using this framework we are capable of performing change-impact static analysis on a program's source code. In other words, we are able to prove the properties induced by changes to a given program before applying these changes. Our contribution is two-fold; we show how to use Lewis' logic of counterfactuals to prove that proposed changes to a program preserve its correctness. We report the development of an automated tool based on resolution and theorem proving for performing code change-impact analysis.

We present a novel execution environment for multi-agent systems building on concepts from cloud computing and peer-to-peer networks. The novel environment can provide the computing power of a cloud for multi-agent systems in intermittently connected networks. We present the design and implementation of a prototype operating system for managing the environment. The operating system provides the user with a consistent view of a single machine, a single file system, and a unified programming model while providing elasticity and availability.

We combine static analysis techniques with model- based deductive verification using SMT solvers to provide a framework that, given an analysis aspect of the source code, automatically generates an analyzer capable of inferring information about that aspect. The analyzer is generated by translating the collecting semantics of a program to a "marked" formula in first order logic over multiple underlying theories. The "marking" can be thought of as a set of holes or contexts corresponding to the "uninterpreted" APIs invoked in the program. Just as a program imports packages and uses methods from classes in those packages, we import the semantics of the API invocations as first order logic assertions. These assertions constitute the models used by the analyzer. Logical specification of the desired program behavior (rather its negation) is incorporated as a first order logic formula. An SMT-LIB formula solver treats the combined formula as a "constraint" and "solves" it. The "solved form" can be used to identify logical (security) errors in Java (Android) programs. Security properties of Android are represented as constraints and the analysis aims to show that these constraints are respected.

In this paper we present a framework for what-if analysis of programs based on Lewis' theory of counterfactuals. The framework can be used to statically perform change impact analysis for source code. It enables us to verify assertions about a changed version of the program without actually incorporating the changes. We present a logical calculus that precisely characterizes structural modifications to source code and their impact on the behavior of the program.

In this short paper, we provide the background to counterfactual logic and give very general suggestions on how we could employ this logic to help us reason about security policies. It seems very appropriate to use this kind of logic to anticipate a change that will compromise the security concerns of a given system before actually applying the changes.

In this paper, we present a formal framework for developing distributed service-oriented systems in an event-driven secure synchronous programming environment. More precisely, we present a synchronous programming language called SOL (Secure Operations Language) that has (i) capabilities for handling service invocations asynchronously, (ii) strong typing to ensure enforcement of information flow and security policies, and (iii) the ability to deal with failures (both benign and byzantine) of components. SOL is supported by formal operational semantics. Applications written in our framework can be verified using formal static checking techniques like theorem proving. The framework runs on the top of the SINS (secure infrastructure for networked systems) infrastructure that we have developed.

Service-oriented systems are distributed systems which have the major advantage of enabling rapid composition of distributed applications, regardless of the programming languages and platforms used in developing and running different components of the applications. In these systems, various capabilities are provided by different organizations as services interconnected by various types of networks. The services can be integrated following a specific workflow to achieve a mission goal for users. For large-scale service-based systems involving multiple organizations, high confidence and adaptability are of prime concern in order to ensure that users can use these systems anywhere, anytime with various devices, knowing that their confidentiality and privacy are well protected and the systems will adapt to satisfy their needs in various situations. Hence, these systems must be adaptable, situation-aware and secure. In this paper, an approach to rapid development of adaptable situation-aware secure service-based (AS/sup 3/) systems is presented. Our approach enables users to rapidly generate, discover, compose services into processes to achieve their goals based on the situation and adapt these processes when situation changes.

A result checker is a program that checks the output of the computation of the observed program for correctness. Introduced originally by Blum, the result checking paradigm has provided a powerful platform assuring the reliability of software. However, constructing result checkers for most problems requires not only significant domain knowledge but also ingenuity and can be error prone. In this paper we present our experience in validating result checkers using formal methods. We have conducted several case studies in validating result checkers from the commercial LEDA system for combinatorial and geometric computing. In one of our case studies, we detected a logical error in a result checker for a program computing max flow of a graph.