Publications

Refine Results

(Filters Applied) Clear All

PATHATTACK: attacking shortest paths in complex networks

Summary

Shortest paths in complex networks play key roles in many applications. Examples include routing packets in a computer network, routing traffic on a transportation network, and inferring semantic distances between concepts on the World Wide Web. An adversary with the capability to perturb the graph might make the shortest path between two nodes route traffic through advantageous portions of the graph (e.g., a toll road he owns). In this paper, we introduce the Force Path Cut problem, in which there is a specific route the adversary wants to promote by removing a minimum number of edges in the graph. We show that Force Path Cut is NP-complete, but also that it can be recast as an instance of the Weighted Set Cover problem, enabling the use of approximation algorithms. The size of the universe for the set cover problem is potentially factorial in the number of nodes. To overcome this hurdle, we propose the PATHATTACK algorithm, which via constraint generation considers only a small subset of paths|at most 5% of the number of edges in 99% of our experiments. Across a diverse set of synthetic and real networks, the linear programming formulation of Weighted Set Cover yields the optimal solution in over 98% of cases. We also demonstrate a time/cost tradeoff using two approximation algorithms and greedy baseline methods. This work provides a foundation for addressing similar problems and expands the area of adversarial graph mining beyond recent work on node classification and embedding.
READ LESS

Summary

Shortest paths in complex networks play key roles in many applications. Examples include routing packets in a computer network, routing traffic on a transportation network, and inferring semantic distances between concepts on the World Wide Web. An adversary with the capability to perturb the graph might make the shortest path...

READ MORE

Health-informed policy gradients for multi-agent reinforcement learning

Summary

This paper proposes a definition of system health in the context of multiple agents optimizing a joint reward function. We use this definition as a credit assignment term in a policy gradient algorithm to distinguish the contributions of individual agents to the global reward. The health-informed credit assignment is then extended to a multi-agent variant of the proximal policy optimization algorithm and demonstrated on simple particle environments that have elements of system health, risk-taking, semi-expendable agents, and partial observability. We show significant improvement in learning performance compared to policy gradient methods that do not perform multi-agent credit assignment.
READ LESS

Summary

This paper proposes a definition of system health in the context of multiple agents optimizing a joint reward function. We use this definition as a credit assignment term in a policy gradient algorithm to distinguish the contributions of individual agents to the global reward. The health-informed credit assignment is then...

READ MORE

Mobile capabilities for micro-meteorological predictions: FY20 Homeland Protection and Air Traffic Control Technical Investment Program

Published in:
MIT Lincoln Laboratory Report TIP-146

Summary

Existing operational numerical weather forecast systems are geographically too coarse and not sufficiently accurate to adequately support future needs in applications such as Advanced Air Mobility, Unmanned Aerial Systems, and wildfire forecasting. This is especially true with respect to wind forecasts. Principal factors contributing to this are the lack of observation data within the atmospheric boundary layer and numerical forecast models that operate on low-resolution grids. This project endeavored to address both of these issues. Firstly, by development and demonstration of specially equipped fixed-wing drones to collect atmospheric data within the boundary layer, and secondly by creating a high-resolution weather research forecast model executing on the Lincoln Laboratory Supercomputing Center. Some success was achieved in the development and flight testing of the specialized drones. Significant success was achieved in the development of the high-resolution forecasting system and demonstrating the feasibility of ingesting atmospheric observations from small airborne platforms.
READ LESS

Summary

Existing operational numerical weather forecast systems are geographically too coarse and not sufficiently accurate to adequately support future needs in applications such as Advanced Air Mobility, Unmanned Aerial Systems, and wildfire forecasting. This is especially true with respect to wind forecasts. Principal factors contributing to this are the lack of...

READ MORE

Combating Misinformation: HLT Highlights from MIT Lincoln Laboratory

Published in:
Human Language Technology Conference (HLTCon), 16-18 March 2021.

Summary

Dr. Joseph Campbell shares several human language technologies highlights from MIT Lincoln Laboratory. These include key enabling technologies in combating misinformation to link personas, analyze content, and understand human networks. Developing operationally relevant technologies requires access to corresponding data with meaningful evaluations, as Dr. Douglas Reynolds presented in his keynote. As Dr. Danelle Shah discussed in her keynote, it’s crucial to develop these technologies to operate at deeper levels than the surface. Producing reliable information from the fusion of missing and inherently unreliable information channels is paramount. Furthermore, the dynamic misinformation environment and the coevolution of allied methods with adversarial methods represent additional challenges
READ LESS

Summary

Dr. Joseph Campbell shares several human language technologies highlights from MIT Lincoln Laboratory. These include key enabling technologies in combating misinformation to link personas, analyze content, and understand human networks. Developing operationally relevant technologies requires access to corresponding data with meaningful evaluations, as Dr. Douglas Reynolds presented in his keynote...

READ MORE

Combating Misinformation: What HLT Can (and Can't) Do When Words Don't Say What They Mean

Author:
Published in:
Human Language Technology Conference (HLTCon), 16-18 March 2021.

Summary

Misinformation, disinformation, and “fake news” have been used as a means of influence for millennia, but the proliferation of the internet and social media in the 21st century has enabled nefarious campaigns to achieve unprecedented scale, speed, precision, and effectiveness. In the past few years, there has been significant recognition of the threats posed by malign influence operations to geopolitical relations, democratic institutions and processes, public health and safety, and more. At the same time, the digitization of communication offers tremendous opportunities for human language technologies (HLT) to observe, interpret, and understand this publicly available content. The ability to infer intent and impact, however, remains much more elusive.
READ LESS

Summary

Misinformation, disinformation, and “fake news” have been used as a means of influence for millennia, but the proliferation of the internet and social media in the 21st century has enabled nefarious campaigns to achieve unprecedented scale, speed, precision, and effectiveness. In the past few years, there has been significant recognition...

READ MORE

Multilayer microhydraulic actuators with speed and force configurations

Author:
Published in:
Microsyst. Nanoeng., Vol. 7, Art. No. 22, 2021.

Summary

Electrostatic motors have traditionally required high voltage and provided low torque, leaving them with a vanishingly small portion of the motor application space. The lack of robust electrostatic motors is of particular concern in microsystems because inductive motors do not scale well to small dimensions. Often, microsystem designers have to choose from a host of imperfect actuation solutions, leading to high voltage requirements or low efficiency and thus straining the power budget of the entire system. In this work, we describe a scalable three-dimensional actuator technology that is based on the stacking of thin microhydraulic layers. This technology offers an actuation solution at 50 volts, with high force, high efficiency, fine stepping precision, layering, low abrasion, and resistance to pull-in instability. Actuator layers can also be stacked in different configurations trading off speed for force, and the actuator improves quadratically in power density when its internal dimensions are scaled-down.
READ LESS

Summary

Electrostatic motors have traditionally required high voltage and provided low torque, leaving them with a vanishingly small portion of the motor application space. The lack of robust electrostatic motors is of particular concern in microsystems because inductive motors do not scale well to small dimensions. Often, microsystem designers have to...

READ MORE

Learning emergent discrete message communication for cooperative reinforcement learning

Published in:
37th Conf. on Uncertainty in Artificial Intelligence, UAI 2021, early access, 26-30 July 2021.

Summary

Communication is a important factor that enables agents work cooperatively in multi-agent reinforcement learning (MARL). Most previous work uses continuous message communication whose high representational capacity comes at the expense of interpretability. Allowing agents to learn their own discrete message communication protocol emerged from a variety of domains can increase the interpretability for human designers and other agents. This paper proposes a method to generate discrete messages analogous to human languages, and achieve communication by a broadcast-and-listen mechanism based on self-attention. We show that discrete message communication has performance comparable to continuous message communication but with much a much smaller vocabulary size. Furthermore, we propose an approach that allows humans to interactively send discrete messages to agents.
READ LESS

Summary

Communication is a important factor that enables agents work cooperatively in multi-agent reinforcement learning (MARL). Most previous work uses continuous message communication whose high representational capacity comes at the expense of interpretability. Allowing agents to learn their own discrete message communication protocol emerged from a variety of domains can increase...

READ MORE

More than a fair share: Network Data Remanence attacks against secret sharing-based schemes [early access]

Published in:
Network and Distributed Systems Security Symp., NDSS, 23-26 February 2021.

Summary

With progress toward a practical quantum computer has come an increasingly rapid search for quantum-safe, secure communication schemes that do not rely on discrete logarithm or factorization problems. One such encryption scheme, Multi-path Switching with Secret Sharing (MSSS), combines secret sharing with multi-path switching to achieve security as long as the adversary does not have global observability of all paths and thus cannot capture enough shares to reconstruct messages. MSSS assumes that sending a share on a path is an atomic operation and all paths have the same delay. In this paper, we identify a side-channel vulnerability for MSSS, created by the fact that in real networks, sending a share is not an atomic operation as paths have multiple hops and different delays. This channel, referred to as Network Data Remanence (NDR), is present in all schemes like MSSS whose security relies on transfer atomicity and all paths having same delay. We demonstrate the presence of NDR in a physical testbed. We then identify two new attacks that aim to exploit the side channel, referred to as NDR Blind and NDR Planned, propose an analytical model to analyze the attacks, and demonstrate them using an implementation of MSSS based on the ONOS SDN controller. Finally, we present a countermeasure for the attacks and show its effectiveness in simulations and Mininet experiments.
READ LESS

Summary

With progress toward a practical quantum computer has come an increasingly rapid search for quantum-safe, secure communication schemes that do not rely on discrete logarithm or factorization problems. One such encryption scheme, Multi-path Switching with Secret Sharing (MSSS), combines secret sharing with multi-path switching to achieve security as long as...

READ MORE

Beyond expertise and roles: a framework to characterize the stakeholders of interpretable machine learning and their needs

Published in:
Proc. Conf. on Human Factors in Computing Systems, 8-13 May 2021, article no. 74.

Summary

To ensure accountability and mitigate harm, it is critical that diverse stakeholders can interrogate black-box automated systems and find information that is understandable, relevant, and useful to them. In this paper, we eschew prior expertise- and role-based categorizations of interpretability stakeholders in favor of a more granular framework that decouples stakeholders' knowledge from their interpretability needs. We characterize stakeholders by their formal, instrumental, and personal knowledge and how it manifests in the contexts of machine learning, the data domain, and the general milieu. We additionally distill a hierarchical typology of stakeholder needs that distinguishes higher-level domain goals from lower-level interpretability tasks. In assessing the descriptive, evaluative, and generative powers of our framework, we find our more nuanced treatment of stakeholders reveals gaps and opportunities in the interpretability literature, adds precision to the design and comparison of user studies, and facilitates a more reflexive approach to conducting this research.
READ LESS

Summary

To ensure accountability and mitigate harm, it is critical that diverse stakeholders can interrogate black-box automated systems and find information that is understandable, relevant, and useful to them. In this paper, we eschew prior expertise- and role-based categorizations of interpretability stakeholders in favor of a more granular framework that decouples...

READ MORE

Seasonal Inhomogeneous Nonconsecutive Arrival Process Search and Evaluation

Published in:
25th International Conference on Pattern Recognition [submitted]

Summary

Time series often exhibit seasonal patterns, and identification of these patterns is essential to understanding thedata and predicting future behavior. Most methods train onlarge datasets and can fail to predict far past the training data. This limitation becomes more pronounced when data is sparse. This paper presents a method to fit a model to seasonal time series data that maintains predictive power when data is limited. This method, called SINAPSE, combines statistical model fitting with an information criteria to search for disjoint, andpossibly nonconsecutive, regimes underlying the data, allowing for a sparse representation resistant to overfitting.
READ LESS

Summary

Time series often exhibit seasonal patterns, and identification of these patterns is essential to understanding thedata and predicting future behavior. Most methods train onlarge datasets and can fail to predict far past the training data. This limitation becomes more pronounced when data is sparse. This paper presents a method to...

READ MORE