Smart home devices are becoming increasingly complex and data-rich. The inevitable repair of these devices will be both difficult and privacy-sensitive. A "HandyTech"—a technician for home Internet of Things (IoT) system repair—has the potential to lower barriers to repair, but privacy questions remain: Are people willing to use a HandyTech to fix a broken home IoT device despite the inherent privacy risk (i.e., allowing a third party to access potentially sensitive IoT data)? We explore this question through a vignette-based, multi-factorial survey with a nationally representative sample of adults in the United States. We further ask whether types of devices (i.e., smart speakers, refrigerators, and CPAP machines) and factors adjacent to privacy and associated with the HandyTech's work (i.e., scope of access, state-based licensing requirements, and transparency provisions) affect decisions to use or not use a HandyTech. We find that some demographic groups are more willing than others to use a HandyTech (e.g., younger age groups, those with children in the home). Current ownership of more types of smart devices increases willingness to use a HandyTech, while greater concerns over general IoT privacy decreases willingness to use a HandyTech. Device-specific perceptions also mattered, such that perceived urgency to fix is strongly associated with willingness to use a HandyTech, but concern over that device's privacy is not. In addition, reduced scope of access and increased transparency by the HandyTech statistically increased willingness to use a HandyTech. In closing, we recommend takeaways that developers and policymakers can engage with to decrease privacy concerns and increase the adoption of third-party IoT repair.

The number of Internet of Things (IoT) devices in smart homes is increasing. This broad adoption facilitates users’ lives, but it also brings problems. One such issue is that some IoT devices may invade users’ privacy through obscure data collection practices or hidden devices. Specific IoT devices can exist out of sight and still collect user data to send to third parties via the Internet. Owners can easily forget the location or even the existence of these devices, especially if the owner is a landlord managing several properties. The landlord-owner scenario creates multi-user problems as designers typically build IoT devices for single users. We developed tag models that use wireless protocols, buzzers, and LED lighting to guide users toward the hidden device in shared spaces and accommodate multi-user scenarios. They are attached to IoT devices inside a residential unit during their installation to be later discovered by a tenant. These tags are similar to Tile models or Airtag but have different features based on our privacy use case. For instance, our tags do not require pairing; multiple users can interact with them through our Android application. Our tags can also embed the IoT device’s information while protecting against unwanted access to that information through a proximity requirement. Researchers have developed several other tools, such as thermal cameras or virtual reality (VR), for discovering devices, but we focused on wireless technologies. We measured specific performance metrics of our tags to analyze their feasibility for this problem. We also conducted a user study to measure the participants’ comfort levels while finding objects with our tags attached. Our results indicate that wireless tags can be viable for device tracking in residential properties.

Recent advances in machine learning have largely benefited from the massive accessible training data. However, large-scale data sharing has raised great privacy concerns. In this work, we propose a novel privacy-preserving data Generative model based on the PATE framework (G-PATE), aiming to train a scalable differentially private data generator that preserves high generated data utility. Our approach leverages generative adversarial nets to generate data, combined with private aggregation among different discriminators to ensure strong privacy guarantees. Compared to existing approaches, G-PATE significantly improves the use of privacy budgets. In particular, we train a student data generator with an ensemble of teacher discriminators and propose a novel private gradient aggregation mechanism to ensure differential privacy on all information that flows from teacher discriminators to the student generator. In addition, with random projection and gradient discretization, the proposed gradient aggregation mechanism is able to effectively deal with high-dimensional gradient vectors. Theoretically, we prove that G-PATE ensures differential privacy for the data generator. Empirically, we demonstrate the superiority of G-PATE over prior work through extensive experiments. We show that G-PATE is the first work being able to generate high-dimensional image data with high data utility under limited privacy budgets ($\varepsilon \le 1$). Our code is available at https://github.com/AI-secure/G-PATE.

In machine learning Trojan attacks, an adversary trains a corrupted model that obtains good performance on normal data but behaves maliciously on data samples with certain trigger patterns. Several approaches have been proposed to detect such attacks, but they make undesirable assumptions about the attack strategies or require direct access to the trained models, which restricts their utility in practice.This paper addresses these challenges by introducing a Meta Neural Trojan Detection (MNTD) pipeline that does not make assumptions on the attack strategies and only needs black-box access to models. The strategy is to train a meta-classifier that predicts whether a given target model is Trojaned. To train the meta-model without knowledge of the attack strategy, we introduce a technique called jumbo learning that samples a set of Trojaned models following a general distribution. We then dynamically optimize a query set together with the meta-classifier to distinguish between Trojaned and benign models.We evaluate MNTD with experiments on vision, speech, tabular data and natural language text datasets, and against different Trojan attacks such as data poisoning attack, model manipulation attack, and latent attack. We show that MNTD achieves 97% detection AUC score and significantly outperforms existing detection approaches. In addition, MNTD generalizes well and achieves high detection performance against unforeseen attacks. We also propose a robust MNTD pipeline which achieves around 90% detection AUC even when the attacker aims to evade the detection with full knowledge of the system.

Logs generated by systems and applications contain a wide variety of heterogeneous information that is important for performance profiling, failure detection, and security analysis. There is a strong need for sharing the logs among different parties to outsource the analysis or to improve system and security research. However, sharing logs may inadvertently leak confidential or proprietary information. Besides sensitive information that is directly saved in logs, such as user-identifiers and software versions, indirect evidence like performance metrics can also lead to the leakage of sensitive information about the physical machines and the system. In this work, we introduce a game-based definition of the risk of exposing sensitive information through released logs. We propose log indistinguishability, a property that is met only when the logs leak little information about the protected sensitive attributes. We design an end-to-end framework that allows a user to identify risk of information leakage in logs, to protect the exposure with log redaction and obfuscation, and to release the logs with a much lower risk of exposing the sensitive attribute. Our framework contains a set of statistical tests to identify violations of the log indistinguishability property and a variety of obfuscation methods to prevent the leakage of sensitive information. The framework views the log-generating process as a black-box and can therefore be applied to different systems and processes. We perform case studies on two different types of log datasets: Spark event log and hardware counters. We show that our framework is effective in preventing the leakage of the sensitive attribute with a reasonable testing time and an acceptable utility loss in logs.

Membership Inference Attacks (MIAs) aim to determine the presence of a record in a machine learning model's training data by querying the model. Recent work has demonstrated the effectiveness of MIA on various machine learning models and corresponding defenses have been proposed. However, both attacks and defenses have focused on an adversary that indiscriminately attacks all the records without regard to the cost of false positives or negatives. In this work, we revisit membership inference attacks from the perspective of a pragmatic adversary who carefully selects targets and make predictions conservatively. We design a new evaluation methodology that allows us to evaluate the membership privacy risk at the level of individuals and not only in aggregate. We experimentally demonstrate that highly vulnerable records exist even when the aggregate attack precision is close to 50% (baseline). Specifically, on the MNIST dataset, our pragmatic adversary achieves a precision of 95.05% whereas the prior attack only achieves a precision of 51.7%.

Internet of Things (IoT) deployments are becoming increasingly automated and vastly more complex. Facilitated by programming abstractions such as trigger-action rules, end-users can now easily create new functionalities by interconnecting their devices and other online services. However, when multiple rules are simultaneously enabled, complex system behaviors arise that are difficult to understand or diagnose. While history tells us that such conditions are ripe for exploitation, at present the security states of trigger-action IoT deployments are largely unknown. In this work, we conduct a comprehensive analysis of the interactions between trigger-action rules in order to identify their security risks. Using IFTTT as an exemplar platform, we first enumerate the space of inter-rule vulnerabilities that exist within trigger-action platforms. To aid users in the identification of these dangers, we go on to present iRuler, a system that performs Satisfiability Modulo Theories (SMT) solving and model checking to discover inter-rule vulnerabilities within IoT deployments. iRuler operates over an abstracted information flow model that represents the attack surface of an IoT deployment, but we discover in practice that such models are difficult to obtain given the closed nature of IoT platforms. To address this, we develop methods that assist in inferring trigger-action information flows based on Natural Language Processing. We develop a novel evaluative methodology for approximating plausible real-world IoT deployments based on the installation counts of 315,393 IFTTT applets, determining that 66% of the synthetic deployments in the IFTTT ecosystem exhibit the potential for inter-rule vulnerabilities. Combined, these efforts provide the insight into the real-world dangers of IoT deployment misconfigurations.

With the growing adoption of machine learning, sharing of learned models is becoming popular. However, in addition to the prediction properties the model producer aims to share, there is also a risk that the model consumer can infer other properties of the training data the model producer did not intend to share. In this paper, we focus on the inference of global properties of the training data, such as the environment in which the data was produced, or the fraction of the data that comes from a certain class, as applied to white-box Fully Connected Neural Networks (FCNNs). Because of their complexity and inscrutability, FCNNs have a particularly high risk of leaking unexpected information about their training sets; at the same time, this complexity makes extracting this information challenging. We develop techniques that reduce this complexity by noting that FCNNs are invariant under permutation of nodes in each layer. We develop our techniques using representations that capture this invariance and simplify the information extraction task. We evaluate our techniques on several synthetic and standard benchmark datasets and show that they are very effective at inferring various data properties. We also perform two case studies to demonstrate the impact of our attack. In the first case study we show that a classifier that recognizes smiling faces also leaks information about the relative attractiveness of the individuals in its training set. In the second case study we show that a classifier that recognizes Bitcoin mining from performance counters also leaks information about whether the classifier was trained on logs from machines that were patched for the Meltdown and Spectre attacks.

Nowadays the camera has developed into an indispensable and ubiquitous part of our life. It ensures the safety of people and their belongings, keeps records of special moments, or logs daily life. However, the ever-increasing amount of cameras surrounding us raised privacy concerns among people, who find themselves easily captured by a camera without themselves acknowledging it. To make matters worse, cameras, especially those on smart phones, are now more pervasive than ever before and can hardly be regulated as the recorders have full control of their cameras. Motivated by the privacy challenges originated from the ever-increasing and wide-spreading cameras, this paper presents the Real-time, Secure, and Privacy-aware Video Redaction System (ReSPonSe), which aims at protecting private information in personal videos according to permissions of people-in-video for other viewers to view them in the video. This system innovatively separates the production of videos into two stages: Encapsulation and Decapsulation. The first stage produces neutral videos in real-time while the second stage provides privacy-aware video to the viewer revealing private content of people-in-video who grants access rights to that viewer. The evaluation demonstrates the capability of this system to protect private information in videos with high efficiency and accuracy.

Existing techniques on adversarial malware generation employ feature mutations based on feature vectors extracted from malware. However, most (if not all) of these techniques suffer from a common limitation: feasibility of these attacks is unknown. The synthesized mutations may break the inherent constraints posed by code structures of the malware, causing either crashes or malfunctioning of malicious payloads. To address the limitation, we present Malware Recomposition Variation (MRV), an approach that conducts semantic analysis of existing malware to systematically construct new malware variants for malware detectors to test and strengthen their detection signatures/models. In particular, we use two variation strategies (i.e., malware evolution attack and malware confusion attack) following structures of existing malware to enhance feasibility of the attacks. Upon the given malware, we conduct semantic-feature mutation analysis and phylogenetic analysis to synthesize mutation strategies. Based on these strategies, we perform program transplantation to automatically mutate malware bytecode to generate new malware variants. We evaluate our MRV approach on actual malware variants, and our empirical evaluation on 1,935 Android benign apps and 1,917 malware shows that MRV produces malware variants that can have high likelihood to evade detection while still retaining their malicious behaviors. We also propose and evaluate three defense mechanisms to counter MRV.

Side-channel risks of Intel's SGX have recently attracted great attention. Under the spotlight is the newly discovered page-fault attack, in which an OS-level adversary induces page faults to observe the page-level access patterns of a protected process running in an SGX enclave. With almost all proposed defense focusing on this attack, little is known about whether such efforts indeed raises the bar for the adversary, whether a simple variation of the attack renders all protection ineffective, not to mention an in-depth understanding of other attack surfaces in the SGX system. In the paper, we report the first step toward systematic analyses of side-channel threats that SGX faces, focusing on the risks associated with its memory management. Our research identifies 8 potential attack vectors, ranging from TLB to DRAM modules. More importantly, we highlight the common misunderstandings about SGX memory side channels, demonstrating that high frequent AEXs can be avoided when recovering EdDSA secret key through a new page channel and fine-grained monitoring of enclave programs (at the level of 64B) can be done through combining both cache and cross-enclave DRAM channels. Our findings reveal the gap between the ongoing security research on SGX and its side-channel weaknesses, redefine the side-channel threat model for secure enclaves, and can provoke a discussion on when to use such a system and how to use it securely.

A new development of smart-home systems is to use mobile apps to control IoT devices across a Home Area Network (HAN). As verified in our study, those systems tend to rely on the Wi-Fi router to authenticate other devices. This treatment exposes them to the attack from malicious apps, particularly those running on authorized phones, which the router does not have information to control. Mitigating this threat cannot solely rely on IoT manufacturers, which may need to change the hardware on the devices to support encryption, increasing the cost of the device, or software developers who we need to trust to implement security correctly. In this work, we present a new technique to control the communication between the IoT devices and their apps in a unified, backward-compatible way. Our approach, called HanGuard, does not require any changes to the IoT devices themselves, the IoT apps or the OS of the participating phones. HanGuard uses an SDN-like approach to offer fine-grained protection: each phone runs a non-system userspace Monitor app to identify the party that attempts to access the protected IoT device and inform the router through a control plane of its access decision; the router enforces the decision on the data plane after verifying whether the phone should be allowed to talk to the device. We implemented our design over both Android and iOS (> 95% of mobile OS market share) and a popular router. Our study shows that HanGuard is both efficient and effective in practice.

Releasing full data records is one of the most challenging problems in data privacy. On the one hand, many of the popular techniques such as data de-identification are problematic because of their dependence on the background knowledge of adversaries. On the other hand, rigorous methods such as the exponential mechanism for differential privacy are often computationally impractical to use for releasing high dimensional data or cannot preserve high utility of original data due to their extensive data perturbation. This paper presents a criterion called plausible deniability that provides a formal privacy guarantee, notably for releasing sensitive datasets: an output record can be released only if a certain amount of input records are indistinguishable, up to a privacy parameter. This notion does not depend on the background knowledge of an adversary. Also, it can efficiently be checked by privacy tests. We present mechanisms to generate synthetic datasets with similar statistical properties to the input data and the same format. We study this technique both theoretically and experimentally. A key theoretical result shows that, with proper randomization, the plausible deniability mechanism generates differentially private synthetic data. We demonstrate the efficiency of this generative technique on a large dataset; it is shown to preserve the utility of original data with respect to various statistical analysis and machine learning measures.

From pencils to commercial aircraft, every man-made object must be designed and manufactured. When it is cheaper or easier to steal a design or a manufacturing process specification than to invent one's own, the incentive for theft is present. As more and more manufacturing data comes online, incidents of such theft are increasing. In this paper, we present a side-channel attack on manufacturing equipment that reveals both the form of a product and its manufacturing process, i.e., exactly how it is made. In the attack, a human deliberately or accidentally places an attack-enabled phone close to the equipment or makes or receives a phone call on any phone nearby. The phone executing the attack records audio and, optionally, magnetometer data. We present a method of reconstructing the product's form and manufacturing process from the captured data, based on machine learning, signal processing, and human assistance. We demonstrate the attack on a 3D printer and a CNC mill, each with its own acoustic signature, and discuss the commonalities in the sensor data captured for these two different machines. We compare the quality of the data captured with a variety of smartphone models. Capturing data from the 3D printer, we reproduce the form and process information of objects previously unknown to the reconstructors. On average, our accuracy is within 1 mm in reconstructing the length of a line segment in a fabricated object's shape and within 1 degree in determining an angle in a fabricated object's shape. We conclude with recommendations for defending against these attacks.

In-app embedded browsers are commonly used by app developers to display web content without having to redirect the user to heavy-weight web browsers. Just like the conventional web browsers, embedded browsers can allow the execution of web code. In addition, they provide mechanisms (viz., JavaScript bridges) to give web code access to internal app code that might implement critical functionalities and expose device resources. This is intrinsically dangerous since there is currently no means for app developers to perform origin-based access control on the JavaScript bridges, and any web code running in an embedded browser is free to use all the exposed app and device resources. Previous work that addresses this problem provided access control solutions that work only for apps that are built using hybrid frameworks. Additionally, these solutions focused on protecting only the parts of JavaScript bridges that expose permissions-protected resources. In this work, our goal is to provide a generic solution that works for all apps that utilize embedded web browsers and protects all channels that give access to internal app and device resources. Towards realizing this goal, we built Draco, a uniform and fine-grained access control framework for web code running on Android embedded browsers (viz., WebView). Draco provides a declarative policy language that allows developers to define policies to specify the desired access characteristics of web origins in a fine-grained fashion, and a runtime system that dynamically enforces the policies. In contrast with previous work, we do not assume any modifications to the Android operating system, and implement Draco in the Chromium Android System WebView app to enable seamless deployment. Our evaluation of the the Draco runtime system shows that Draco incurs negligible overhead, which is in the order of microseconds.

We study the new mobile query auto-completion (QAC) problem to exploit mobile devices' exclusive signals, such as those related to mobile applications (apps). We propose AppAware, a novel QAC model using installed app and recently opened app signals to suggest queries for matching input prefixes on mobile devices. To overcome the challenge of noisy and voluminous signals, AppAware optimizes composite objectives with a lighter processing cost at a linear rate of convergence. We conduct experiments on a large commercial data set of mobile queries and apps. Installed app and recently opened app signals consistently and significantly boost the accuracy of various baseline QAC models on mobile devices.

Query auto-completion (QAC) facilitates user query composition by suggesting queries given query prefix inputs. In 2014, global users of Yahoo! Search saved more than 50% keystrokes when submitting English queries by selecting suggestions of QAC. Users' preference of queries can be inferred during user-QAC interactions, such as dwelling on suggestion lists for a long time without selecting query suggestions ranked at the top. However, the wealth of such implicit negative feedback has not been exploited for designing QAC models. Most existing QAC models rank suggested queries for given prefixes based on certain relevance scores.

OBJECTIVE: The capability to share data, and harness its potential to generate knowledge rapidly and inform decisions, can have transformative effects that improve health. The infrastructure to achieve this goal at scale--marrying technology, process, and policy--is commonly referred to as the Learning Health System (LHS). Achieving an LHS raises numerous scientific challenges. MATERIALS AND METHODS: The National Science Foundation convened an invitational workshop to identify the fundamental scientific and engineering research challenges to achieving a national-scale LHS. The workshop was planned by a 12-member committee and ultimately engaged 45 prominent researchers spanning multiple disciplines over 2 days in Washington, DC on 11-12 April 2013. RESULTS: The workshop participants collectively identified 106 research questions organized around four system-level requirements that a high-functioning LHS must satisfy. The workshop participants also identified a new cross-disciplinary integrative science of cyber-social ecosystems that will be required to address these challenges. CONCLUSIONS: The intellectual merit and potential broad impacts of the innovations that will be driven by investments in an LHS are of great potential significance. The specific research questions that emerged from the workshop, alongside the potential for diverse communities to assemble to address them through a 'new science of learning systems', create an important agenda for informatics and related disciplines.

Motivated by privacy and usability requirements in various scenarios where existing cryptographic tools (like secure multi-party computation and functional encryption) are not adequate, we introduce a new cryptographic tool called Controlled Functional Encryption (C-FE). As in functional encryption, C-FE allows a user (client) to learn only certain functions of encrypted data, using keys obtained from an authority. However, we allow (and require) the client to send a fresh key request to the authority every time it wants to evaluate a function on a ciphertext. We obtain efficient solutions by carefully combining CCA2 secure public-key encryption (or rerandomizable RCCA secure public-key encryption, depending on the nature of security desired) with Yao's garbled circuit. Our main contributions in this work include developing and for- mally defining the notion of C-FE; designing theoretical and practical constructions of C-FE schemes achieving these definitions for specific and general classes of functions; and evaluating the performance of our constructions on various application scenarios.

One of the greatest challenges an organization faces is determining when an employee is permitted to utilize a certain resource in a system. This "insider threat" can be addressed through two strategies: i) prospective methods, such as access control, that make a decision at the time of a request, and ii) retrospective methods, such as post hoc auditing, that make a decision in the light of the knowledge gathered afterwards. While it is recognized that each strategy has a distinct set of benefits and drawbacks, there has been little investigation into how to provide system administrators with practical guidance on when one or the other should be applied. To address this problem, we introduce a framework to compare these strategies on a common quantitative scale. In doing so, we translate these strategies into classification problems using a context-based feature space that assesses the likelihood that an access request is legitimate. We then introduce a technique called bispective analysis to compare the performance of the classification models under the situation of non-equivalent costs for false positive and negative instances, a significant extension on traditional cost analysis techniques, such as analysis of the receiver operator characteristic (ROC) curve. Using domain-specific cost estimates and access logs of several months from a large Electronic Medical Record (EMR) system, we demonstrate how bispective analysis can support meaningful decisions about the relative merits of prospective and retrospective decision making for specific types of hospital personnel.

Developments in health information technology have encouraged the establishment of distributed systems known as Health Information Exchanges (HIEs) to enable the sharing of patient records between institutions. In many cases, the parties running these exchanges wish to limit the amount of information they are responsible for holding because of sensitivities about patient information. Hence, there is an interest in broker-based HIEs that keep limited information in the exchange repositories. However, it is essential to audit these exchanges carefully due to risks of inappropriate data sharing. In this paper, we consider some of the requirements and present a design for auditing broker-based HIEs in a way that controls the information available in audit logs and regulates their release for investigations. Our approach is based on formal rules for audit and the use of Hierarchical Identity-Based Encryption (HIBE) to support staged release of data needed in audits and a balance between automated and manual reviews. We test our methodology via an extension of a standard for auditing HIEs called the Audit Trail and Node Authentication Profile (ATNA) protocol.

Anonymized user datasets are often released for research or indus-try applications. As an example, t.qq.com released its anonymized users ’ profile, social interaction, and recommendation log data in KDD Cup 2012 to call for recommendation algorithms. Since the entities (users and so on) and edges (links among entities) are of multiple types, the released social network is a heterogeneous in-formation network. Prior work has shown how privacy can be com-promised in homogeneous information networks by the use of spe-cific types of graph patterns. We show how the extra information derived from heterogeneity can be used to relax these assumptions. To characterize and demonstrate this added threat, we formally de-fine privacy risk in an anonymized heterogeneous information net-work to identify the vulnerability in the possible way such data are released, and further present a new de-anonymization attack that exploits the vulnerability. Our attack successfully de-anonymized most individuals involved in the data—for an anonymized 1,000-user t.qq.com network of density 0.01, the attack precision is over 90 % with a 2.3-million-user auxiliary network.

Dynamic Searchable Symmetric Encryption allows a client to store a dynamic collection of encrypted documents with a server, and later quickly carry out keyword searches on these encrypted documents, while revealing minimal information to the server. In this paper we present a new dynamic SSE scheme that is simpler and more efficient than existing schemes while revealing less information to the server than prior schemes, achieving fully adaptive security against honest-but-curious servers. We implemented a prototype of our scheme and demonstrated its efficiency on datasets from prior work. Apart from its concrete efficiency, our scheme is also simpler: in particular, it does not require the server to support any operation other than upload and download of data. Thus the server in our scheme can be based solely on a cloud storage service, rather than a cloud computation service as well, as in prior work. In building our dynamic SSE scheme, we introduce a new primitive called Blind Storage, which allows a client to store a set of files on a remote server in such a way that the server does not learn how many files are stored, or the lengths of the individual files, as each file is retrieved, the server learns about its existence (and can notice the same file being downloaded subsequently), but the file's name and contents are not revealed. This is a primitive with several applications other than SSE, and is of independent interest.

The design of Android is based on a set of unprotected shared resources, including those inherited from Linux (e.g., Linux public directories). However, the dramatic development in Android applications (app for short) makes available a large amount of public background information (e.g., social networks, public online services), which can potentially turn such originally harmless resource sharing into serious privacy breaches. In this paper, we report our work on this important yet understudied problem. We discovered three unexpected channels of information leaks on Android: per-app data-usage statistics, ARP information, and speaker status (on or off). By monitoring these channels, an app without any permission may acquire sensitive information such as smartphone user's identity, the disease condition she is interested in, her geo-locations and her driving route, from top-of-the-line Android apps. Furthermore, we show that using existing and new techniques, this zero-permission app can both determine when its target (a particular application) is running and send out collected data stealthily to a remote adversary. These findings call into question the soundness of the design assumptions on shared resources, and demand effective solutions. To this end, we present a mitigation mechanism for achieving a delicate balance between utility and privacy of such resources.

There has been considerable success in developing strategies to detect insider threats in information systems based on what one might call the random object access model or ROA. This approach models illegitimate users as ones who randomly access records. The goal is to use statistics, machine learning, knowledge of workflows and other techniques to support an anomaly detection framework that finds such users. In this paper we introduce and study a random topic access model or RTA aimed at users whose access may be illegitimate but is not fully random because it is focused on common semantic themes. We argue that this model is appropriate for a meaningful range of attacks and develop a system based on topic summarization that is able to formalize the model and provide anomalous user detection effectively for it. To this end, we use healthcare as an example and propose a framework for evaluating the ability to recognize various types of random users called random topic access detection or RTAD. Specifically, we utilize a combination of Latent Dirichlet Allocation (LDA), for feature extraction, a k-nearest neighbor (k-NN) algorithm for outlier detection and evaluate the ability to identify different adversarial types. We validate the technique in the context of hospital audit logs where we show varying degrees of success based on user roles and the anticipated characteristics of attackers. In particular, it was found that RTAD exhibits strong performance for roles are described by a few topics, but weaker performance when users are more topic-agnostic.

In role-based access control (RBAC), roles are traditionally defined as sets of permissions. Roles specified by administrators may be inaccurate, however, such that data mining methods have been proposed to learn roles from actual permission utilization. These methods minimize variation from an information theoretic perspective, but they neglect the expert knowledge of administrators. In this paper, we propose a strategy to enable a controlled evolution of RBAC based on utilization. To accomplish this goal, we extend a subset enumeration framework to search candidate roles for an RBAC model that addresses an objective function which balances administrator beliefs and permission utilization. The rate of role evolution is controlled by an administrator-specified parameter. To assess effectiveness, we perform an empirical analysis using simulations, as well as a real world dataset from an electronic medical record system (EMR) in use at a large academic medical center (over 8000 users, 140 roles, and 140 permissions). We compare the results with several state-of-the-art role mining algorithms using 1) an outlier detection method on the new roles to evaluate the homogeneity of their behavior and 2)a set-based similarity measure between the original and new roles. The results illustrate our method is comparable to the state-of-the-art, but allows for a range of RBAC models which tradeoff user behavior and administrator expectations. For instance, in the EMR dataset, we find the resulting RBAC model contains 22% outliers and a distance of 0.02 to the original RBAC model when the system is biased toward administrator belief, and 13% outliers and a distance of 0.26 to the original RBAC model when biased toward permission utilization.

Denial-of-service (DoS) attacks are considered within the province of a shared channel model in which attack rates may be large but are bounded and client request rates vary within fixed bounds. In this setting, it is shown that clients can adapt effectively to an attack by increasing their request rate based on timeout windows to estimate attack rates. The server will be able to process client requests with high probability while pruning out most of the attack by selective random sampling. The protocol introduced here, called Adaptive Selective Verification (ASV), is shown to use bandwidth efficiently and does not require any server state or assumptions about network congestion. The main results of the paper are a formulation of optimal performance and a proof that ASV is optimal.

We consider reliable telemetry in white spaces in the form of protecting the integrity of distributed spectrum measurements against coordinated misreporting attacks. Our focus is on the case where a subset of the sensors can be remotely attested. We propose a practical framework for using statistical sequential estimation coupled with machine learning classifiers to deter attacks and achieve quantifiably precise outcome. We provide an application-oriented case study in the context of spectrum measurements in the white spaces. The study includes a cost analysis for remote attestation, as well as an evaluation using real transmitter and terrain data from the FCC and NASA for Southwest Pennsylvania. The results show that with as low as 15% penetration of attestation-capable nodes, more than 94% of the attempts from omniscient attackers can be thwarted.

Attribute-based Access Control (ABAC) based on XACML can substantially improve the security and management of access rights on databases. However, existing implementations rely on high-level policy interpretation and are not as efficient as mechanisms natively supported by commodity databases. In this paper we explore advantages and challenges arising from compiling XACML policies for database access into Access Control Lists (ACLs) natively supported by the database. The main contributions are an architecture and algorithms for efficiently addressing incremental changes in attributes that could trigger changes to the ACLs. We consider this in a context of reflective database access control where attributes used in access decisions are stored in the database itself. Our implementation and experiments demonstrate a significant improvement in access decision times compared to the best available optimizations for general XACML access engines.

In this paper, we propose countermeasures to mitigate damage caused by spoofing attacks in Delay-Tolerant Networks (DTNs). In our model, an attacker spoofs someone else's address (the victim's) to absorb packets from the network intended for that victim. Address spoofing is arguably a very severe attack in DTNs, compared to other known attacks, such as dropping packets. Without a Public Key Infrastructure in DTNs, providing protection against this attack is challenging. We propose SPREAD (countermeasure against SPoofing by REplica ADjustment), a solution that assesses evidence of spoofing and offers countermeasures designed for quota-based multi-copy routing protocols. Our solution relies on reducing the weight of packet copies, charged to the routing quota, when these packets are given to a node suspected of spoofing. The weight reduction increases as spoofing evidence mounts against a node. The approach is designed to probabilistically maintain the same number of packet copies in the network as would be the case in the absence of attacks, despite the actual occurrence of spoofing. We show that SPREAD makes DTNs robust against spoofing attacks, does not overburden the network, and limits the overall overhead within a certain bound.

Troubleshooting unresponsive sensor nodes is a significant challenge in remote sensor network deployments. This paper introduces the tele-diagnostic powertracer, an in-situ troubleshooting tool that uses external power measurements to determine the internal health condition of an unresponsive host and the most likely cause of its failure. We developed our own low-cost power meter with low-bandwidth radio to report power measurements and findings, hence allowing remote (i.e., tele-) diagnosis. The tool was deployed and tested in a remote solar-powered sensing network for acoustic and visual environmental monitoring. It was shown to successfully distinguish between several categories of failures that cause unresponsive behavior including energy depletion, antenna damage, radio disconnection, system crashes, and anomalous reboots. It was also able to determine the internal health conditions of an unresponsive node, such as the presence or absence of sensing and data storage activities (for each of multiple sensors). The paper explores the feasibility of building such a remote diagnostic tool from the standpoint of economy, scale and diagnostic accuracy. To the authors' knowledge, this is the first paper that presents a remote diagnostic tool that uses power measurements to diagnose sensor system failures.

Attribute-Based Messaging (ABM) enables messages to be addressed using attributes of recipients rather than an explicit list of recipients. Such messaging offers benefits of efficiency, exclusiveness, and intensionality, but faces challenges in access control and confidentiality. In this article we explore an approach to intraenterprise ABM based on providing access control and confidentiality using information from the same attribute database exploited by the addressing scheme. We show how to address three key challenges. First, we demonstrate a manageable access control system based on attributes. Second, we demonstrate use of attribute-based encryption to provide end-to-end confidentiality. Third, we show that such a system can be efficient enough to support ABM for mid-size enterprises. Our implementation can dispatch confidential ABM messages approved by XACML policy review for an enterprise of at least 60,000 users with only seconds of latency.

Publish-subscribe (pub-sub) systems are useful for many applications, including pervasive environments. In the latter context, however, great care must be taken to preserve the privacy of sensitive information, such as users' location and activities. Traditional access control schemes provide at best a partial solution, since they do not capture potential inference regarding sensitive data that a subscriber may make. We propose a logic-based pub-sub system, where inference rules are used to both derive high-level events for use in applications as well as specify potentially harmful inferences that could be made regarding data. We provide a formal definition of safety in such a system that captures the possibility of indirect information flows. We show that the safety problem is co-NP-complete; however, problems of realistic size can be reduced to a satisfiability problem that can be efficiently decided by a SAT solver.

With the growth in the popularity of social networking sites like Facebook and MySpace, there is an increasing concern about privacy of content posted by users. Many users enter personal details about themselves but have poor understanding of theats such as identity theft and stalking. There is a need to educate and assist users in understanding how their personal data is exposed to other users. In this paper, we introduce the concept of negotiated audit which gives users of social networks valuable feedback about how their data is being used. Our design has three levels of auditing for both sharing and browsing data: no audit, complete audit and anonymous audit. Users can classify their data as requiring some level of auditing and can also set their browsing preference to one of the auditing levels. Users can only see some data if their browsing preference is compatible with the data's audit level thus giving rise to negotiation of how much users are willing to reveal about their activities and how much data they will be able to access. We provide a mathematical model and describe a simple social networking prototype called Sh@re that implements negotiated audit.

The nine papers in this special issue focus on network infrastructure configuration and some of the problems encountered in the areas of specification, diagnosis, repair, synthesis, and anonymization.

Reflective Database Access Control (RDBAC) is a model in which a database privilege is expressed as a database query itself, rather than as a static privilege contained in an access control list. RDBAC aids the management of database access controls by improving the expressiveness of policies. However, such policies introduce new interactions between data managed by different users, and can lead to unexpected results if not carefully written and analyzed. We propose the use of Transaction Datalog as a formal framework for expressing reflective access control policies. We demonstrate how it provides a basis for analyzing certain types of policies and enables secure implementations that can guarantee that configurations built on these policies cannot be subverted.

We consider Denial of Service (DoS) attacks within the province of a shared channel model in which attack rates may be large but are bounded and client request rates vary within fixed bounds. In this setting it is shown that the clients can respond effectively to an attack by using bandwidth as a payment scheme and time-out windows to adaptively boost request rates. The server will be able to process client requests with high probability while pruning out most of the attack by selective random sampling. Our protocol, which we call Adaptive Selective Verification (ASV) is shown to be efficient in terms of bandwidth consumption using both a theoretical model and network simulations. It differs from previously-investigated adaptive mechanisms for bandwidth-based payment by requiring very limited state on the server.

There has been excellent progress on languages for rigorously describing key exchange protocols and techniques for proving that the network security tunnels they establish preserve confidentiality and integrity. New problems arise in describing and analyzing establishment protocols and tunnels when they are used as building blocks to achieve high-level security goals for network administrative domains. We introduce a language called the tunnel calculus and associated analysis techniques that can address functional problems arising in the concurrent establishment of tunnels. In particular, we use the tunnel calculus to explain and resolve cases where interleavings of establishment messages can lead to deadlock. Deadlock can be avoided by making unwelcome security compromises, but we prove that it can be eliminated systematically without such compromises using a concept of session to relate tunnels. Our main results are noninterference and progress theorems familiar to the concurrency community, but not previously applied to tunnel establishment protocols.

Constraint systems provide techniques for automatically analyzing the conformance of low-level access control policies to high-level business rules formalized as logical constraints. However, there are likely to be priorities for solutions that are not easy to encode formally, so administrator input is often important. This paper introduces PolicyMorph, a constraint system that supports interactive development and maintenance of access control policies that respect both formalized and un-formalized business rules and priorities. We provide a mathematical description of the system and an architecture for implementing it. We constructed a prototype that is validated using a case study in which constraints are imposed on a building automation system that controls door locks. PolicyMorph advances the state-of-the-art in constraint systems by suggesting predictable policy model modifications that will resolve specific constraint violations and then allowing policy administrators to select the appropriate modifications using knowledge that is not formally encoded in the constraint system.

Firewall policy management is challenging and error-prone. While ample research has led to tools for policy specification, correctness analysis, and optimization, few researchers have paid attention to firewall policy deployment: the process where a management tool edits a firewall's configuration to make it run the policies specified in the tool. In this paper, we provide the first formal definition and theoretical analysis of safety in firewall policy deployment. We show that naive deployment approaches can easily create a temporary security hole by permitting illegal traffic, or interrupt service by rejecting legal traffic during the deployment. We define safe and most-efficient deployments, and introduce the shuffling theorem as a formal basis for constructing deployment algorithms and proving their safety. We present efficient algorithms for constructing most-efficient deployments in popular policy editing languages. We show that in certain widely- installed policy editing languages, a safe deployment is not always possible. We also show how to leverage existing diff algorithms to guarantee a safe, most- efficient, and monotonic deployment in other editing languages.

Several power-aware routing schemes have been developed for wireless networks under the assumption that nodes are willing to sacrifice their power reserves in the interest of the network as a whole. But, in several applications of practical utility, nodes are organized in groups, and as a result, a node is willing to sacrifice in the interest of other nodes in its group but not necessarily for nodes outside its group. Such groups arise naturally as sets of nodes associated with a single owner or task. We consider the premise that groups will share resources with other groups only if each group experiences a reduction in power consumption. Then, the groups may form a coalition in which they route each other's packets. We demonstrate that sharing between groups has different properties from sharing between individuals and investigate fair, mutually beneficial sharing between groups. In particular, we propose a Pareto-efficient condition for group sharing based on max-min fairness called fair coalition routing. We propose distributed algorithms for computing the fair coalition routing. Using these algorithms, we demonstrate that fair coalition routing allows different groups to mutually beneficially share their resources

Attribute based messaging (ABM) enables message senders to dynamically create a list of recipients based on their attributes as inferred from an enterprise database. Such targeted messaging can reduce unnecessary communications and enhance privacy, but faces challenges in access control. In this paper, we explore an approach to ABM based on deriving access control information from the same attribute database exploited by the addressing scheme. We show how to address three key challenges. First, we demonstrate a manageable access control system based on attributes. Second we show how this can be used with existing messaging systems to provide a practical deployment strategy. Third, we show that such a system can be efficient enough to support ABM for mid-size enterprises. Our implementation can dispatch ABM messages approved by XACML review for an enterprise of at least 60,000 users with only seconds of latency

There is a growing interest in establishing rules to regulate the privacy of citizens in the treatment of sensitive personal data such as medical and financial records. Such rules must be respected by software used in these sectors. The regulatory statements are somewhat informal and must be interpreted carefully in the software interface to private data. This paper describes techniques to formalize regulatory privacy rules and how to exploit this formalization to analyze the rules automatically. Our formalism, which we call privacy APIs, is an extension of access control matrix operations to include (1) operations for notification and logging and (2) constructs that ease the mapping between legal and formal language. We validate the expressive power of privacy APIs by encoding the 2000 and 2003 HIPAA consent rules in our system. This formalization is then encoded into Promela and we validate the usefulness of the formalism by using the SPIN model checker to verify properties that distinguish the two versions of HIPAA

Advances in networking, sensors, and embedded devices have made it feasible to monitor and provide medical and other assistance to people in their homes. Aging populations will benefit from reduced costs and improved healthcare through assisted living based on these technologies. However, these systems challenge current state-of-the-art techniques for usability, reliability, and security. This is a particular challenge for open and extensible systems that combine software and hardware from many vendors and provide information to diverse clinicians. In this paper we present the I-Living architecture for assisted living that allows independent parties work together in a dependable, secure, and low-cost fashion with predictable properties. Our approach is based on an Assisted Living Service Provider (ALSP) who provides a server that collects and maintains encrypted assisted persons (APs)' records. Our ALSP can be a third party distinct from APs, communication providers, and clinicians; or it can be part of an ISP, hospital or similar enterprise. We have explored the architecture by developing a collection of applications and implementing them in a prototype system. Our system shows the feasibility and opportunity of an open approach to assisted living systems.

Web services offer an opportunity to redesign a variety of older systems to exploit the advantages of a flexible, extensible, secure set of standards. In this paper we explore the objective of improving Internet messaging (email) by redesigning it as a family of Web services, an approach we call WSEmail. We illustrate an architecture and describe some applications. Since increased flexibility often mitigates against security and performance, we focus on steps for proving security properties and measuring the performance of our system with its security operations. In particular, we demonstrate an automated proof using TulaFale and ProVerif of a correspondence theorem for an application called on-demand attachments. We also provide performance measures for the basic WSEmail functions in a prototype we have implemented using .NET. Our experiments show a latency of about a quarter of a second per transaction under load.

Embedded devices like smartcards can now run multiple interacting applications. A particular challenge in this domain is to dynamically integrate diverse security policies. In this paper we show how a framework based on a concise formal model lets us securely customize a payment card equipped with a programmable chip. We present policy automata, a formal model of computations that grant or deny access to a resource. This model combines defeasible logic with state machines, representing complex policies as combinations of simpler modular policies. We use the model in a framework for specifying, merging and analyzing modular policies. This framework is implemented as Polaris, a tool which analyzes policy automata to reveal potential conflicts or redundancies, and compiles automata into Java Card applets.

In this paper we develop a language of mobile agents called uPLAN for describing the capabilities of active (programmable) networks. We use a formal semantics for uPLAN to demonstrate how capabilities provided for programming the network can affect t

We explore the challenges for making the programming interfaces for embedded devices open and safe, and present a prototype architecture for delivering verified programs using barcodes. In particular, we consider programs for microwave ovens, which provide a basic open API for controlling cooking times. In our architecture, recipes are written in Java, and their safety properties are formally verified using the model checker Spin. We use off-the-shelf utilities for compressing the byte code, and use two-dimensional barcodes for program delivery. We report on experiments that demonstrate the feasibility of the proposed architecture for predictability and delivery.

We show how to use an interactive theorem prover, HOL, together with a model checker, SPIN, to prove key properties of distance vector routing protocols. We do three case studies: correctness of the RIP standard, a sharp real-time bound on RIP stability, and preservation of loop-freedom in AODV, a distance vector protocol for wireless networks. We develop verification techniques suited to routing protocols generally. These case studies show significant benefits from automated support in reduced verification workload and assistance in finding new insights and gaps for standard specifications.

Network protocols are often analyzed using simulations. We demonstrate how to extend such simulations to check propositions expressing safety properties of network event traces in an extended form of linear temporal logic. Our technique uses the INS simulator together with a component of the MaC system to provide a uniform framework. We demonstrate its effectiveness by analyzing simulations of the ad hoc on-demand distance vector (AODV) routing protocol for packet radio networks. Our analysis finds violations of significant properties and we discuss the faults that cause them. Novel aspects of our approach include modest integration costs with other simulation objectives such as performance evaluation, greatly increased flexibility in specifying properties to be checked and techniques for analyzing complex traces of alarms raised by the monitoring software.

We consider the problem of monitoring an interactive device, such as an implementation of a network protocol, in order to check whether its execution is consistent with its specification. At rst glance, it appears that a monitor could simply follow the input-output trace of the device and check it against the specification. However, if the monitor is able to observe inputs and outputs only from a vantage point external to the device---as is typically the case---the problem becomes surprisingly difficult. This is because events may be bu ered, and even lost, between the monitor and the device, in which case, even for a correctly running device, the trace observed at the monitor could be inconsistent with the specification.In this paper, we formulate the problem of external monitoring as a language recognition problem. Given a specification that accepts a certain language of input-output sequences, we de ne another language that corresponds to input-output sequences observable externally. We also give an algorithm to check membership of a string in the derived language. It turns out that without any assumptions on the specification, this algorithm may take unbounded time and space. To address this problem, we de ne a series of properties of device specifications or protocols that can be exploited to construct e cient language recognizers at the monitor. We characterize these properties and provide complexity bounds for monitoring in each case.To illustrate our methodology, we describe properties of the Internet Transmission Control Protocol (TCP), and identify features of the protocol that make it challenging to monitor e ciently.

We develop a language of mobile agents called uPLAN for describing the capabilities of active (programmable) networks. We use a formal semantics for uPLAN to demonstrate how capabilities provided for programming the network can affect the potential flows of information between users. In particular, we formalize a concept of security against attacks on secrecy by an 'outsider' and show how basic protections are preserved in the presence of programmable network functions such as user-customized labeled routing.

Why are there so few successful "real-world" programming and testing tools based on academic research? This talk focuses on program analysis tools, and proposes a surprisingly simple explanation with interesting ramifications.

We introduce a language for creating and manipulating certificates, that is, digitally signed data based on public key cryptography, and a system for revoking certificates. Our approach provides a uniform mechanism for secure distribution of public key bindings, authorizations, and revocation information. An external language for the description of these and other forms of data is compiled into an intermediate language with a well-defined denotational and operational semantics. The internal language is used to carry out consistency checks for security, and optimizations for efficiency. Our primary contribution is a technique for treating revocation data dually to other sorts of information using a polarity discipline in the intermediate language.

Any large scale security architecture that uses certificates to provide security in a distributed system will need some automated support for moving certificates around in the network. We believe that for efficiency, this automated support should be tied closely to the consumer of the certificates: the policy verifier. As a proof of concept, we have built QCM, a prototype policy language and verifier that can direct a retrieval mechanism to obtain certificates from the network. Like previous verifiers, QCM takes a policy and certificates supplied by a requester and determines whether the policy is satisfied. Unlike previous verifiers, QCM can take further action if the policy is not satisfied: QCM can examine the policy to decide what certificates might help satisfy it and obtain them from remote servers on behalf of the requester. This takes place automatically, without intervention by the requester; there is no additional burden placed on the requester or the policy writer for the retrieval service we provide. We present examples that show how our technique greatly simplifies certificate-based secure applications ranging from key distribution to ratings systems, and that QCM policies are simple to write. We describe our implementation, and illustrate the operation of the prototype. Copyright © 2000 John Wiley & Sons, Ltd.

This article studies an abstract model of dependencies between software configuration items based on a theory of concurrent computation over a class of Petri nets called production nets. A general theory of build optimizations and their correctness is developed based on a form of abstract interpretation called a build abstraction ; these are created during a build and are used to optimize subsequent builds. Various examples of such optimizations are discussed. The theory is used to show how properties can be characterized and proved, and how optimizations can be composed and compared.

We present PLANet: an active network architecture and implementation. In addition to a standard suite of Internet-like services, PLANet has two key programmability features: (1) all packets contain programs; and (2) router functionality may be extended dynamically. Packet programs are written in our special purpose programming language PLAN, the Packet Language for Active Networks, while dynamic router extensions are written in OCaml, a dialect of ML. Currently, PLANet routers run as byte-code-interpreted Linux user-space applications, and support Ethernet and IP as link layers. PLANet achieves respectable performance on standard networking operations: on 300 MHz Pentium-II's attached to 100 Mbps Ethernet, PLANet can route 48 Mbps and switch over 5000 packets per second. We demonstrate the utility of PLANet's activeness by showing experimentally how it can nontrivially improve application and aggregate network performance in congested conditions.

PLAN (Packet Language for Active Networks) is a new language for programs that form the packets of a programmable network. These programs replace the packet headers (which can be viewed as very rudimentary programs) used in current networks. As such, PLAN programs are lightweight and of restricted functionality. These limitations are mitigated by allowing PLAN code to call node-resident service routines written in other, more powerful languages. This two-level architecture, in which PLAN serves as a scripting or 'glue' language for more general services, is the primary contribution of this paper. We have successfully applied the PLAN programming environment to implement an IP-free internetwork.PLAN is based on the simply typed lambda calculus and provides a restricted set of primitives and datatypes. PLAN defines a special construct called a chunk used to describe the remote execution of PLAN programs on other nodes. Primitive operations on chunks are used to provide basic data transport in the network and to support layering of protocols. Remote execution can make debugging difficult, so PLAN provides strong static guarantees to the programmer, such as type safety. A more novel property aimed at protecting network availability is a guarantee that PLAN programs use a bounded amount of network resources.

We demonstrate how order-theoretic abstractions can be useful in identifying, formalizing, and exploiting relationships between seemingly dissimilar AI algorithms that perform computations on partially-ordered sets. In particular, we show how the order-theoretic concept of an anti-chain can be used to provide an efficient representation for such sets when they satisfy certain special properties. We use anti-chains to identify and analyze the basic operations and representation optimizations in the version space learning algorithm and the assumption-based truth maintenance system (ATMS). Our analysis allows us to (1) extend the known theory of admissibility of concept spaces for incremental version space merging, and (2) develop new, simpler label-update algorithms for ATMSs with DNF assumption formulas.

This paper studies an abstract model of dependencies between software configuration items based on a theory of concurrent computation over a class of Petri nets. The primary goal is to illustrate the descriptive power of the model and lay theoretical groundwork for using it to design software configuration maintenance tools or model software configurations. As a start in this direction, the paper analyzes and addresses certain limitations in make description files using a form of abstract interpretation.

Abstract We develop an operational model for a language based on linear logic. Our semantics is ‘low-level’ enough to express sharing and copying while still being ‘high-level’ enough to abstract away from details of memory layout, and thus can be used to test potential applications of linear logic for analysis of programs. In particular, we demonstrate a precise relationship between type correctness for the linear-logic-based language and the correctness of a reference-counting interpretation of the primitives, and formulate and prove a result describing the possible run-time reference counts of values of linear type.

This paper introduces an operator M called the mixed powerdomain which generalizes the convex (Plotkin) powerdomain. The construction is based on the idea of representing partial information about a set of data items using a pair of sets, one representing partial information in the manner of the upper (Smyth) powerdomain and the other in the manner of the lower (Hoare) powerdomain where the components of such pairs are required to satisfy a consistency condition. This provides a richer family of meaningful partial descriptions than are available in the convex powerdomain and also makes it possible to include the empty set in a satisfactory way. The new construct is given a rigorous mathematical treatment like that which has been applied to the known powerdomains. It is proved that M is a continuous functor on bifinite domains which is left adjoint to the forgetful functor from a category of continuous structures called mix algebras. For a domain D with a coherent Scott topology, elements of MD can be represented as pairs (U, V) where U ⊆ D is a compact upper set, V ⊆ D is a closed set and the downward closure of U ⌢ V is equal to V. A Stone dual characterization of M is also provided.

We present a method for providing semantic interpretations for languages with a type system featuring inheritance polymorphism. Our approach is illustrated on an extension of the language Fun of Cardelli and Wegner, which we interpret via a translation into an extended polymorphic lambda calculus. Our goal is to interpret inheritances in Fun via coercion functions which are definable in the target of the translation. Existing techniques in the theory of semantic domains can be then used to interpret the extended polymorphic lambda calculus, thus providing many models for the original language. This technique makes it possible to model a rich type discipline which includes parametric polymorphism and recursive types as well as inheritance. A central difficulty in providing interpretations for explicit type disciplines featuring inheritance in the sense discussed in this paper arises from the fact that programs can type-check in more than one way. Since interpretations follow the type-checking derivations, coherence theorems are required: that is, one must prove that the meaning of a program does not depend on the way it was type-checked. Proofs of such theorems for our proposed interpretation are the basic technical results of this paper. Interestingly, proving coherence in the presence of recursive types, variants, and abstract types forced us to reexamine fundamental equational properties that arise in proof theory (in the form of commutative reductions) and domain theory (in the form of strict vs. non-strict functions).

The relevance of a form of cut elimination theorem for linear logic tensor theories to the concept of a process on a Petri net is discussed. The discussion is based on two definitions of processes given by E. Best and R. Devillers (1987). Their notions of process correspond to equivalence relations on linear logic proofs. It is noted that the cut reduced proofs form a process under the finer of these definitions. Using a strongly normalizing rewrite system and a weak Church-Rosser theorem, it is shown that each class of the coarser process definition contains exactly one of these finer classes which can therefore be viewed as a canonical or normal process representative. The relevance of these rewrite rules to the categorical approach of P. Degano et al. (1989) is also discussed.>

The purpose of this paper is to discuss the relationship between the interpretations of non-deterministic programs using the upper (total correctness) powerdomain on the one hand and the lower (partial correctness) powerdomain on the other. It is shown that there is a close semantic relationship between these two interpretations which suggests the formulation of a new operator called the mixed powerdomain. It is shown that the mixed powerdomain has many pleasing domain-theoretic and algebraic properties. The mixed powerdomain is closely related to new powerdomains which have been recently investigated as mathematical models of partial information in databases. Some of the basic intuitions captured by such structures may have uses for the specification of non-deterministic computations. The paper includes a sample non-deterministic programming language and a semantics using the mixed powerdomain.

A method is presented for providing semantic interpretations for languages which feature inheritance in the framework of statically checked, rich type disciplines. The approach is illustrated by an extension of the language Fun of L. Cardelli and P. Wegner (1985), which is interpreted via a translation into an extended polymorphic lambda calculus. The approach interprets inheritances in Fun as coercion functions already definable in the target of the translation. Existing techniques in the theory of semantic domains can then be used to interpret the extended polymorphic lambda calculus, thus providing many models for the original language. The method allows the simultaneous modeling of parametric polymorphism, recursive types, and inheritance, which has been regarded as problematic because of the seemingly contradictory characteristics of inheritance and type recursion on higher types. The main difficulty in providing interpretations for explicit type disciplines featuring inheritance is identified. Since interpretations follow the type-checking derivations, coherence theorems are required, and the authors prove them for their semantic method.>

Almost all of the categories normally used as a mathematical foundation for denotational semantics satisfy a condition known as consistent completeness. The authors explore the possibility of using different condition coherence, which has its origin in topology and logic. In particular, they concentrate on posets with principal ideas that are algebraic lattices and with coherent topologies. These form a Cartesian closed category which has fixed points for domain equations. It is shown that a universal domain exists. A categorical treatment of the construction of this domain is provided, and its relationship to other applications discussed.>