In this paper, we propose a novel machine learning technique to detect and correctly classify adversarially modified images. Our approach takes advantage of the adversarial training objective (to influence the prediction with small perturbations to the original image) by searching for large discrepancies in the model’s output relative to the input image. We find clusters in each space, and for an image whose clusters do not agree with each other, we flag the image as potentially adversarial and use the input space cluster’s prediction in place of the attacked model’s output. We have found that this method tends to find adversarial samples which are more likely to be misclassified by the attacked model, and that simply deferring to the input cluster’s prediction on such samples is enough to increase accuracy on adversarial data, even when the attacked model is adversarially trained.

Since the introduction of deep convolutional neural networks (CNNs), object detection in imagery has witnessed substantial breakthroughs in state-of-the-art performance. The defense community utilizes overhead image sensors that acquire large field-of-view aerial imagery in various bands of the electromagnetic spectrum, which is then exploited for various applications, including the detection and localization of man-made objects. In this work, we utilize a recent state-of-the art object detection algorithm, faster R-CNN, to train a deep CNN for vehicle detection in multimodal imagery. We utilize the vehicle detection in aerial imagery (VEDAI) dataset, which contains overhead imagery that is representative of an ISR setting. Our contribution includes modification of key parameters in the faster R-CNN algorithm for this setting where the objects of interest are spatially small, occupying less than 1:5×10-3 of the total image pixels. Our experiments show that (1) an appropriately trained deep CNN leads to average precision rates above 93% on vehicle detection, and (2) transfer learning between imagery modalities is possible, yielding average precision rates above 90% in the absence of fine-tuning.

We present a novel descriptor algorithm (DUDE) using line/point duality and a randomization strategy that provides simple but robust, consistent feature extraction and correspondence. Using duality enables us to effectively capture a distribution of line segments, and the proposed randomization strategy improves repeatability over existing techniques by generating more line features in common between two images. We demonstrate the effectiveness of our approach using a challenging set of disparate image pairs, and show that the DUDE descriptor performs comparably to state-of-the-art methods with significantly less computation expense.

We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2 α balls of half radius. There are two variants of routing-scheme design: (i) labeled (name-dependent) routing, in which the designer is allowed to rename the nodes so that the names (labels) can contain additional routing information, for example, topological information; and (ii) name-independent routing, which works on top of the arbitrary original node names in the network, that is, the node names are independent of the routing scheme. In this article, given any constant ϵ ∈ (0, 1) and an n -node edge-weighted network of doubling dimension α ∈ O (loglog n ), we present —a (1 + ϵ)-stretch labeled compact routing scheme with ⌈log n ⌉-bit routing labels, O (log 2 n /loglog n )-bit packet headers, and ((1/ϵ) O (α) log 3 n )-bit routing information at each node; —a (9 + ϵ)-stretch name-independent compact routing scheme with O (log 2 n /loglog n )-bit packet headers, and ((1/ϵ) O (α) log 3 n )-bit routing information at each node. In addition, we prove a lower bound: any name-independent routing scheme with o ( n (ϵ/60) 2 ) bits of storage at each node has stretch no less than 9 − ϵ for any ϵ ∈ (0, 8). Therefore, our name-independent routing scheme achieves asymptotically optimal stretch with polylogarithmic storage at each node and packet headers. Note that both schemes are scale-free in the sense that their space requirements do not depend on the normalized diameter Δ of the network. We also present a simpler nonscale-free (9 + ϵ)-stretch name-independent compact routing scheme with improved space requirements if Δ is polynomial in n .

We study the compact routing problem in networks whose shortest path metrics are decomposable. Decomposable metrics are more general than doubling metrics, growth-bounded metrics, and metrics induced by graphs excluding Kr,r as a minor. In this work, we present both name-dependent and name-independent constant stretch compact routing schemes for bounded decomposable metrics with polylogarithmic storage requirements at each node and polylogarithmic packet headers. Our work is the first to design compact routing schemes with constant stretch for networks as general as decomposable metrics.

The paper addresses the problem of battery lifetime maximization for a job sequence executing on a processor with discrete voltage/frequency states under a deadline constraint. We consider a nonlinear electrochemical discharging model of the battery, and present a pseudo-polynomial time optimal algorithm and a fully polynomial time approximation algorithm as solutions. This is the first work that proposes both optimal and approximation algorithms for battery aware energy management based on voltage/frequency scaling techniques. Our experimental results show that the approximation algorithms widely outperform an existing technique. Further, for a number of realistic and synthetic benchmarks, the qualities of the solutions produced by our approximation techniques are much better than the required quality bounds imposed by the designer.

For a graph ( V , E ), existing compact linear formulations for the minimum cut problem require Θ(| V || E |) variables and constraints and can be interpreted as a composition of | V | − 1 polyhedra for minimum s - t cuts in much the same way as early approaches to finding globally minimum cuts relied on | V | − 1 calls to a minimum s - t cut algorithm. We present the first formulation to beat this bound, one that uses O (| V | 2 ) variables and O (| V | 3 ) constraints. An immediate consequence of our result is a compact linear relaxation with O (| V | 2 ) constraints and O (| V | 3 ) variables for enforcing global connectivity constraints. This relaxation is as strong as standard cut-based relaxations and has applications in solving traveling salesman problems by integer programming as well as finding approximate solutions for survivable network design problems using Jain's iterative rounding method. Another application is a polynomial-time verifiable certificate of size n for for the NP-complete problem of l 1 -embeddability of a rational metric on an n -set (as opposed to a certificate of size n 2 known previously).

No abstract available.

This paper addresses the automated synthesis of a custom network-on-chip architecture whose topology is optimized for the specific communication requirements of the target device. The optimization objectives include power consumption and resource usage. This paper presents a two-stage synthesis approach consisting of the following: (1) core to router mapping and (2) custom topology and route generation. In particular, it presents an optimal technique for core to router mapping [stage (1)] and a factor-2 approximation algorithm for custom topology generation [stage (2)]. The superior quality of the techniques is established by experimentation with benchmark applications and by comparisons with existing approaches.

The high performance requirements of networking applications has led to the advent of programmable network processor (NP) architectures that incorporate symmetric multiprocessing, and block multi-threading. The paper presents an automated system-level design technique for process mapping on such architectures with an objective of maximizing the worst case throughput of the application. As this mapping must be done in the presence of resource (processors and code size) constraints, this is an NP-complete problem (Ausiello et al., 1999). We present a polynomial time approximation algorithm guaranteed to generate solutions with throughput at least 1/2 that of optimal solutions. The proposed algorithm was utilized to map realistic applications on the Intel IXP2400 (NP) architecture, and produced solutions within 78% of optimal.

Network-on-chip (NoC) architectures with optimized topologies have been shown to be superior to regular architectures (such as mesh) for application specific multiprocessor system-on-chip (MPSoC) devices. The application specific NoC design problem takes as input the system-level floorplan of the computation architecture, characterized library of NoC components, and the communication performance requirements. The objective is to generate an optimized NoC topology, and routes for the communication traces on the architecture such that the performance requirements are satisfied and power consumption is minimized. The paper discusses a two stage automated approach consisting of i) core to router mapping, and ii) topology and route generation for design of custom NoC architectures. In particular it presents an optimal technique for core to router mapping (stage i), and a factor 2 approximation algorithm for custom topology generation (stage ii). The superior quality of the techniques is established by experimentation with benchmark applications, and comparisons with integer linear programming (ILP) formulations, and heuristic techniques.

Threshold logic is gaining prominence as an alternative to Boolean logic. The main reason for this trend is the availability of devices that implement these circuits efficiently (current mode, differential mode circuits), as well as the promise they hold for the future nanoalldevices (RTDs, SETs, QCAs and other nano devices). This has generated renewed interest in the design automation community to design efficient CAD tools for threshold logic. Recently a lot of work has been done to synthesize threshold logic circuits. So far there has been no efficient method to verify the synthesized circuits. In this work we address the problem of combinational equivalence checking for threshold circuits. We propose a new algorithm, to obtain compact functional representation of threshold elements. We give the proof of correctness, and analyze its runtime complexity. We use this polynomial time algorithm to develop a new methodology to verify threshold circuits. We report the result of our experiments, comparing the proposed methodology to the naive approach. We get up to 189X improvement in the run time (23X on average), and could verify circuits that the naive approach could not.

We address power minimization of earliest deadline first and rate monotonic schedules by voltage and frequency scaling. We prove that the problems are NP-hard, and present (1+∈) fully polynomial time approximation techniques that generate solutions which are guaranteed to be within a specified quality bound (QB= ∈) (say within 1% of the optimal). We demonstrate that our techniques can match optimal solutions when QB is set at 1%, out perform existing approaches [1] even when QB is set at 10%, generate solutions that are quite close to optimal (< 5%) even when QB is set at higher values (25%), and execute in a fraction of a second (with QB > 5%) for large 100 node task sets.

We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek name-independent routing schemes with (1+ε) stretch and polylogarithmic storage at each node: since existing lower bound precludes such a scheme, we relax our guarantees to allow for (i) a small fraction of nodes to have large storage, say size of O(n log n) bits, or (ii) a small fraction of source-destination pairs to have larger, but still constant, stretch.

We consider the problem of name-independent routing in doubling metrics. A doubling metric is a metric space whose doubling dimension is a constant, where the doubling dimension of a metric space is the least value α such that any ball of radius r can be covered by at most 2 α balls of radius r/2. Given any δ> 0 and a weighted undirected network G whose shortest path metric d is a doubling metric with doubling dimension α, we present a name-independent routing scheme for G with (9+δ)-stretch, (2+ 1 δ)O(α) (log ∆) 2 (log n)bit routing information at each node, and packet headers of size O(log n), where ∆ is the ratio of the largest to the smallest shortest path distance in G. In addition, we prove that for any ǫ ∈ (0, 8), there is a doubling metric network G with n nodes, doubling dimension α ≤ 6 − log ǫ, and ∆ = O(2 1/ǫ n) such that any name-independent routing scheme on G with routing information at each node of size o(n (ǫ/60)2)-bits has stretch larger than 9 − ǫ. Therefore assuming that ∆ is bounded by a polynomial on n, our algorithm basically achieves optimal stretch for name-independent routing in doubling metrics with packet header size and routing information at each node both bounded by a polylogarithmic function of n.

Application-specific system-on-chip (SoC) design offers the opportunity for incorporating custom network-on-chip (NoC) architectures that are more suitable for a particular application, and do not necessarily conform to regular topologies. This paper presents novel mixed integer linear programming (MILP) formulations for synthesis of custom NoC architectures. The optimization objective of the techniques is to minimize the power consumption subject to the performance constraints. We present a two-stage approach for solving the custom NoC synthesis problem. The power consumption of the NoC architecture is determined by both the physical links and routers. The power consumption of a physical link is dependent upon the length of the link, which in turn, is governed by the layout of the SoC. Therefore, in the first stage, we address the floorplanning problem that determines the locations of the various cores and the routers. In the second stage, we utilize the floorplan from the first stage to generate topology of the NoC and the routes for the various traffic traces. We also present a clustering-based heuristic technique for the second stage to reduce the run times of the MILP formulation. We analyze the quality of the results and solution times of the proposed techniques by extensive experimentation with realistic benchmarks and comparisons with regular mesh-based NoC architectures.

Network-on-chip (NoC) has been proposed as a solution to the communication challenges of system-on-chip (SoC) design in nanoscale technologies. Application specific SoC design offers the opportunity for incorporating custom NoC architectures that are more suitable for a particular application, and do not necessarily conform to regular topologies. Custom NoC design in nanoscale technologies must address performance requirements, power consumption and physical layout considerations. This paper presents a novel three phase technique that i) generates a performance aware layout of the SoC, ii) maps the cores of the SoC to routers, and iii) generates a unique route for every trace that satisfies the performance and architectural constraints. We present an analysis of the quality of the results of the proposed technique by experimentation with realistic benchmarks.

We study ways to restrict or prevent the damage that can be caused in a peer-to-peer network by corrupt entities creating multiple pseudonyms. We show that it is possible to remotely issue certificates that can be used to test the distinctness of identities. To our knowledge, this is the first work that shows that remote anonymous certification of identity is possible under adversarial conditions. Our certification protocols are based on geometric techniques that establish location information in a fault-tolerant and distributed fashion. They do not rely on a centralized certifying authority or infrastructure that has direct knowledge of entities in the system, and work in Euclidean or spherical geometry of arbitrary dimension. Our protocols tolerate corrupt entities, including corrupt certifiers as well as collusion by certification applicants and certifiers. We consider both broadcast and point-to-point message passing models.

Network-on-chip (NoC) has been proposed as a solution for the communication challenges of system-on-chip (SoC) design in the nanoscale regime. SoC design offers the opportunity for incorporating custom NoC architectures that are more suitable for a particular application, and do not necessarily conform to regular topologies. This paper presents novel linear programming based techniques for synthesis of custom NoC architectures. In the nanoscale regime, low power consumption would continue to be an important design goal. We first discuss an optimal mixed integer linear programming (MILP) formulation that synthesizes a low power NoC architecture subject to the performance constraints. The MILP formulation is limited by large run times. We next present heuristic techniques that exploit clustering, and 0-1 constraint relaxation to reduce the run times of the formulation. The techniques minimize power as the primary goal, and minimize the number of routers (area) as a secondary goal. We present an analysis of the quality of the results and the solution times of the proposed techniques by extensive experimentation with the realistic benchmarks. The clustering based heuristic generates results whose power consumption is within 11% of the MILP solutions and its average run time is 171.1 seconds. The average run time of the relaxation and rounding based techniques is less than 2 seconds, and the power consumption of their solutions is within 58% of the MILP result.

We present simple semidefinite programming relaxations for the m-hard minimum bandwidth and minimum length linear ordering problems.We then show how these relaxations can be rounded in a natural way (via random projection) to obtain new approximation guarantees for both of these vertex-ordering problems.