Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 30 of 35
Full-Text Articles in Entire DC Network
Experimenting With Tcpa/Tcg Hardware, Or: How I Learned To Stop Worrying And Love The Bear, John Marchesini, Sean Smith, Omen Wild, Rich Macdonald
Experimenting With Tcpa/Tcg Hardware, Or: How I Learned To Stop Worrying And Love The Bear, John Marchesini, Sean Smith, Omen Wild, Rich Macdonald
Computer Science Technical Reports
Over the last few years, our group has been working on applications of secure coprocessors---but has been frustrated by the limited computational environment and high expense of such devices. Over the last few years, the TCPA (now TCG) has produced a specification for a trusted platform module (TPM)---a small hardware addition intended to improve the overall security of a larger machine (and tied up with a still-murky vision of Windows-based trusted computing). Some commodity desktops now come up with these TPMs. Consequently, we began an experiment to see if (in the absence of a Non-Disclosure Agreement) we could use this …
A Subgroup Algorithm To Identify Cross-Rotation Peaks Consistent With Non-Crystallographic Symmetry, Ryan H. Lilien, Chris Bailey-Kellogg, Amy C. Anderson, Bruce R. Donald
A Subgroup Algorithm To Identify Cross-Rotation Peaks Consistent With Non-Crystallographic Symmetry, Ryan H. Lilien, Chris Bailey-Kellogg, Amy C. Anderson, Bruce R. Donald
Computer Science Technical Reports
Molecular replacement (MR) often plays a prominent role in determining initial phase angles for structure determination by X-ray crystallography. In this paper, an efficient quaternion-based algorithm is presented for analyzing peaks from a cross-rotation function to identify model orientations consistent with non-crystallographic symmetry (NCS), and to generate NCS-consistent orientations missing from the list of cross-rotation peaks. Our algorithm, CRANS, analyzes the rotation differences between each pair of cross-rotation peaks to identify finite subgroups of NCS. Sets of rotation differences satisfying the subgroup axioms correspond to orientations compatible with the correct NCS. The CRANS algorithm was first tested using cross-rotation peaks …
A Probability-Based Similarity Measure For Saupe Alignment Tensors With Applications To Residual Dipolar Couplings In Nmr Structural Biology, Anthony K. Yan, Christopher J. Langmead, Bruce Randall Donald
A Probability-Based Similarity Measure For Saupe Alignment Tensors With Applications To Residual Dipolar Couplings In Nmr Structural Biology, Anthony K. Yan, Christopher J. Langmead, Bruce Randall Donald
Computer Science Technical Reports
High-throughput NMR structural biology and NMR structural genomics pose a fascinating set of geometric challenges. A key bottleneck in NMR structural biology is the resonance assignment problem. We seek to accelerate protein NMR resonance assignment and structure determination by exploiting a priori structural information. In particular, a method known as Nuclear Vector Replacement (NVR) has been proposed as a method for solving the assignment problem given a priori structural information [24,25]. Among several different kinds of input data, NVR uses a particular type of NMR data known as residual dipolar couplings (RDCs). The basic physics of residual dipolar couplings tells …
High-Throughput 3d Homology Detection Via Nmr Resonance Assignment, Christopher James Langmead, Bruce Randall Donald
High-Throughput 3d Homology Detection Via Nmr Resonance Assignment, Christopher James Langmead, Bruce Randall Donald
Computer Science Technical Reports
One goal of the structural genomics initiative is the identification of new protein folds. Sequence-based structural homology prediction methods are an important means for prioritizing unknown proteins for structure determination. However, an important challenge remains: two highly dissimilar sequences can have similar folds --- how can we detect this rapidly, in the context of structural genomics? High-throughput NMR experiments, coupled with novel algorithms for data analysis, can address this challenge. We report an automated procedure, called HD, for detecting 3D structural homologies from sparse, unassigned protein NMR data. Our method identifies 3D models in a protein structural database whose geometries …
An Improved Nuclear Vector Replacement Algorithm For Nuclear Magnetic Resonance Assignment, Christopher James Langmead, Bruce Randall Donald
An Improved Nuclear Vector Replacement Algorithm For Nuclear Magnetic Resonance Assignment, Christopher James Langmead, Bruce Randall Donald
Computer Science Technical Reports
We report an improvement to the Nuclear Vector Replacement (NVR) algorithm for high-throughput Nuclear Magnetic Resonance (NMR) resonance assignment. The new algorithm improves upon our earlier result in terms of accuracy and computational complexity. In particular, the new NVR algorithm assigns backbone resonances without error (100% accuracy) on the same test suite examined in [Langmead and Donald J. Biomol. NMR 2004], and runs in $O(n^{5/2} \log {(cn)})$ time where $n$ is the number of amino acids in the primary sequence of the protein, and $c$ is the maximum edge weight in an integer-weighted bipartite graph.
Bear: An Open-Source Virtual Secure Coprocessor Based On Tcpa, Rich Macdonald, Sean Smith, John Marchesini, Omen Wild
Bear: An Open-Source Virtual Secure Coprocessor Based On Tcpa, Rich Macdonald, Sean Smith, John Marchesini, Omen Wild
Computer Science Technical Reports
This paper reports on our ongoing project to use TCPA to transform a desktop Linux machine into a virtual secure coprocessor: more powerful but less secure than higher-end devices. We use TCPA hardware and modified boot loaders to protect fairly static components, such as a trusted kernel; we use an enforcer module---configured as Linux Security Module---to protected more dynamic system components; we use an encrypted loopback filesystem to protect highly dynamic components. All our code is open source and available under GPL from http://enforcer.sourceforge.net/
Formal Properties Of Linear Memory Types, Heng Huang, Lea Wittie, Chris Hawblitzel
Formal Properties Of Linear Memory Types, Heng Huang, Lea Wittie, Chris Hawblitzel
Computer Science Technical Reports
Efficient low-level systems need more control over memory than safe high-level languages usually provide. As a result, run-time systems are typically written in unsafe languages such as C. This report describes an abstract machine designed to give type-safe code more control over memory. It includes complete definitions and proofs of preservation, progress, strong normalization, erasure, and translation correctness.
Using Caching For Browsing Anonymity, Anna M. Shubina, Sean W. Smith
Using Caching For Browsing Anonymity, Anna M. Shubina, Sean W. Smith
Computer Science Technical Reports
Privacy-providing tools, including tools that provide anonymity, are gaining popularity in the modern world. Among the goals of their users is avoiding tracking and profiling. While some businesses are unhappy with the growth of privacy-enhancing technologies, others can use lack of information about their users to avoid unnecessary liability and even possible harassment by parties with contrary business interests, and to gain a competitive market edge. Currently, users interested in anonymous browsing have the choice only between single-hop proxies and the few more complex systems that are available. These still leave the user vulnerable to long-term intersection attacks. In this …
The Mistaken Axioms Of Wireless-Network Research, David Kotz, Calvin Newport, Chip Elliott
The Mistaken Axioms Of Wireless-Network Research, David Kotz, Calvin Newport, Chip Elliott
Computer Science Technical Reports
Most research on ad-hoc wireless networks makes simplifying assumptions about radio propagation. The ``Flat Earth'' model of the world is surprisingly popular: all radios have circular range, have perfect coverage in that range, and travel on a two-dimensional plane. CMU's ns-2 radio models are better but still fail to represent many aspects of realistic radio networks, including hills, obstacles, link asymmetries, and unpredictable fading. We briefly argue that key ``axioms'' of these types of propagation models lead to simulation results that do not adequately reflect real behavior of ad-hoc networks, and hence to network protocols that may not work well …
Discrete-Event Fluid Modeling Of Background Tcp Traffic, David M. Nicol, Guanhua Yan
Discrete-Event Fluid Modeling Of Background Tcp Traffic, David M. Nicol, Guanhua Yan
Computer Science Technical Reports
TCP is the most widely used transport layer protocol used in the internet today. A TCP session adapts the demands it places on the network to observations of bandwidth availability on the network. Because TCP is adaptive, any model of its behavior that aspires to be accurate must be influenced by other network traffic. This point is especially important in the context of using simulation to evaluate some new network algorithm of interest (e.g. reliable multi-cast) in an environment where the background traffic affects---and is affected by---its behavior. We need to generate background traffic efficiently in a way that captures …
Efficient And Practical Constructions Of Ll/Sc Variables, Prasad Jayanti, Srdjan Petrovic
Efficient And Practical Constructions Of Ll/Sc Variables, Prasad Jayanti, Srdjan Petrovic
Computer Science Technical Reports
Over the past decade, LL/SC have emerged as the most suitable synchronization instructions for the design of lock-free algorithms. However, current architectures do not support these instructions; instead, they support either CAS or RLL/RSC (e.g. POWER4, MIPS, SPARC, IA-64). To bridge this gap, this paper presents two efficient wait-free algorithms for implementing 64-bit LL/SC objects from 64-bit CAS or RLL/RSC objects. Our first algorithm is practical: it has a small, constant time complexity (of 4 for LL and 5 for SC) and a space overhead of only 4 words per process. This algorithm uses unbounded sequence numbers. For theoretical interest, …
Distributed Planning And Control For Modular Robots With Unit-Compressible Modules, Zack Butler, Daniela Rus
Distributed Planning And Control For Modular Robots With Unit-Compressible Modules, Zack Butler, Daniela Rus
Computer Science Technical Reports
Self-reconfigurable robots are versatile systems consisting of large numbers of independent modules. Effective use of these systems requires parallel actuation and planning, both for efficiency and independence from a central controller. This paper presents the PacMan algorithm, a technique for distributed actuation and planning for systems with two- or three-dimensional unit-compressible modules. We give two versions of the algorithm along with correctness analysis. We also analyze the parallel actuation capability of the algorithm, showing that it will not deadlock and will avoid disconnecting the robot. We have implemented PacMan on the Crystal robot, a hardware system developed in our lab, …
A Surface-Based Approach For Classification Of 3d Neuroanatomic Structures, Li Shen, James Ford, Fillia Makedon, Andrew Saykin
A Surface-Based Approach For Classification Of 3d Neuroanatomic Structures, Li Shen, James Ford, Fillia Makedon, Andrew Saykin
Computer Science Technical Reports
We present a new framework for 3D surface object classification that combines a powerful shape description method with suitable pattern classification techniques. Spherical harmonic parameterization and normalization techniques are used to describe a surface shape and derive a dual high dimensional landmark representation. A point distribution model is applied to reduce the dimensionality. Fisher's linear discriminants and support vector machines are used for classification. Several feature selection schemes are proposed for learning better classifiers. After showing the effectiveness of this framework using simulated shape data, we apply it to real hippocampal data in schizophrenia and perform extensive experimental studies by …
Digital Art Forensics, Siwei Lyu, Daniel Rockmore, Hany Farid
Digital Art Forensics, Siwei Lyu, Daniel Rockmore, Hany Farid
Computer Science Technical Reports
We describe a computational technique for digitally authenticating works of art. This approach builds statistical models of an artist from a set of authenticated works. Additional works are then authenticated against this model. The statistical model consists of first- and higher-order wavelet statistics. We show preliminary results from our analysis of thirteen drawings by Pieter Bruegel the Elder. We also present preliminary results showing how these techniques may be applicable to determining how many hands contributed to a single painting.
Efficient Security For Bgp Route Announcements, David M. Nicol, Sean W. Smith, Meiyuan Zhao
Efficient Security For Bgp Route Announcements, David M. Nicol, Sean W. Smith, Meiyuan Zhao
Computer Science Technical Reports
The Border Gateway Protocol (BGP) determines how Internet traffic is routed throughout the entire world; malicious behavior by one or more BGP speakers could create serious security issues. Since the protocol depends on a speaker honestly reporting path information sent by previous speakers and involves a large number of independent speakers, the Secure BGP (S-BGP) approach uses public-key cryptography to ensure that a malicious speaker cannot fabricate this information. However, such public-key cryptography is expensive: S-BGP requires a digital signature operation on each announcement sent to each peer, and a linear (in the length of the path) number of verifications …
Relaxing The Problem-Size Bound For Out-Of-Core Columnsort, Geeta Chaudhry, Elizabeth A. Hamon, Thomas H. Cormen
Relaxing The Problem-Size Bound For Out-Of-Core Columnsort, Geeta Chaudhry, Elizabeth A. Hamon, Thomas H. Cormen
Computer Science Technical Reports
Previous implementations of out-of-core columnsort limit the problem size to $N \leq \sqrt{(M/P)^3 / 2}$, where $N$ is the number of records to sort, $P$ is the number of processors, and $M$ is the total number of records that the entire system can hold in its memory (so that $M/P$ is the number of records that a single processor can hold in its memory). We implemented two variations to out-of-core columnsort that relax this restriction. Subblock columnsort is based on an algorithmic modification of the underlying columnsort algorithm, and it improves the problem-size bound to $N \leq (M/P)^{5/3} / 4^{2/3}$ …
Stupid Columnsort Tricks, Geeta Chaudhry, Thomas H. Cormen
Stupid Columnsort Tricks, Geeta Chaudhry, Thomas H. Cormen
Computer Science Technical Reports
Leighton's columnsort algorithm sorts on an $r \times s$ mesh, subject to the restrictions that $s$ is a divisor of~$r$ and that $r \geq 2s^2$ (so that the mesh is tall and thin). We show how to mitigate both of these restrictions. One result is that the requirement that $s$ is a divisor of~$r$ is unnecessary; columnsort sorts correctly whether or not $s$ divides~$r$. We present two algorithms that, as long as $s$ is a perfect square, relax the restriction that $r \geq 2s^2$; both reduce the exponent of~$s$ to~$3/2$. One algorithm requires $r \geq 4s^{3/2}$ if $s$ divides~$r$ and …
Privacy-Enhanced Credential Services, Alex Iliev, Sean Smith
Privacy-Enhanced Credential Services, Alex Iliev, Sean Smith
Computer Science Technical Reports
The use of credential directories in PKI and authorization systems such as Shibboleth introduces a new privacy risk: an insider at the directory can learn much about otherwise protected interactions by observing who makes queries, and what they ask for. Recent advances in Practical Private Information Retrieval provide promising countermeasures. In this paper, we extend this technology to solve this new privacy problem, and present a design and preliminary prototype for a LDAP-based credential service that can prevent even an insider from learning anything more than the fact a query was made. Our preliminary performance analysis suggests that the complete …
Keyjacking: Risks Of The Current Client-Side Infrastructure, John Marchesini, S W. Smith, Meiyuan Zhao
Keyjacking: Risks Of The Current Client-Side Infrastructure, John Marchesini, S W. Smith, Meiyuan Zhao
Computer Science Technical Reports
In theory, PKI can provide a flexible and strong way to authenticate users in distributed information systems. In practice, much is being invested in realizing this vision via client-side SSL and browser-based keystores. Exploring this vision, we demonstrate that browsers will use personal certificates to authenticate requests that the person neither knew of nor approved (and which password-based systems would have defeated), and we demonstrate the easy permeability of these keystores (including new attacks on medium and high-security IE/XP keys). We suggest some countermeasures, but also suggest that a fundamental rethinking of the trust, usage, and storage model might result …
3d-Structural Homology Detection Via Unassigned Residual Dipolar Couplings, Christopher James Langmead, Bruce Randall Donald
3d-Structural Homology Detection Via Unassigned Residual Dipolar Couplings, Christopher James Langmead, Bruce Randall Donald
Computer Science Technical Reports
Recognition of a protein's fold provides valuable information about its function. While many sequence-based homology prediction methods exist, an important challenge remains: two highly dissimilar sequences can have similar folds --- how can we detect this rapidly, in the context of structural genomics? High-throughput NMR experiments, coupled with novel algorithms for data analysis, can address this challenge. We report an automated procedure for detecting 3D-structural homologies from sparse, unassigned protein NMR data. Our method identifies the 3D-structural models in a protein structural database whose geometries best fit the unassigned experimental NMR data. It does not use sequence information and is …
Tr-2003001: States Of Knowledge And Group Action, Rohit Parikh
Tr-2003001: States Of Knowledge And Group Action, Rohit Parikh
Computer Science Technical Reports
No abstract provided.
Tr-2003008: Learning And Applying Temporal Patterns Through Experience, Esther Lock
Tr-2003008: Learning And Applying Temporal Patterns Through Experience, Esther Lock
Computer Science Technical Reports
No abstract provided.
Tr-2003005: Lambek Calculus Is Np-Complete, Mati Pentus
Tr-2003005: Lambek Calculus Is Np-Complete, Mati Pentus
Computer Science Technical Reports
No abstract provided.
Tr-2003006: Rijndael For Algebraists: An Expanded Version Of Lenstra's Manuscript, Hannes Moritz, Wei Zhu
Tr-2003006: Rijndael For Algebraists: An Expanded Version Of Lenstra's Manuscript, Hannes Moritz, Wei Zhu
Computer Science Technical Reports
No abstract provided.
Tr-2003014: A High-Performance Abstract Machine For Prolog And Its Extensions, Neng-Fa Zhou
Tr-2003014: A High-Performance Abstract Machine For Prolog And Its Extensions, Neng-Fa Zhou
Computer Science Technical Reports
No abstract provided.
Tr-2003010: A Semantic Proof Of The Realizability Of Modal Logic In The Logic Of Proofs, Melvin Fitting
Tr-2003010: A Semantic Proof Of The Realizability Of Modal Logic In The Logic Of Proofs, Melvin Fitting
Computer Science Technical Reports
No abstract provided.
Tr-2003009: A Hierarchical Projection Pursuit Clustering Algorithm, Jayson E. Rome, Alexei D. Miasnikov, Robert M. Haralick
Tr-2003009: A Hierarchical Projection Pursuit Clustering Algorithm, Jayson E. Rome, Alexei D. Miasnikov, Robert M. Haralick
Computer Science Technical Reports
No abstract provided.
Tr-2003015: Two Counterexamples In The Logic Of Dynamic Topological Systems, Sergey Slavnov
Tr-2003015: Two Counterexamples In The Logic Of Dynamic Topological Systems, Sergey Slavnov
Computer Science Technical Reports
No abstract provided.
Tr-2003002: A Knowledge Based Semantics Of Messages, Rohit Parikh, R. Ramanujam
Tr-2003002: A Knowledge Based Semantics Of Messages, Rohit Parikh, R. Ramanujam
Computer Science Technical Reports
No abstract provided.
Tr-2003003: Finite Information Logic, Rohit Parikh, Jouko Väänänen
Tr-2003003: Finite Information Logic, Rohit Parikh, Jouko Väänänen
Computer Science Technical Reports
No abstract provided.