Multithreaded Test Synthesis for Deadlock Detection

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing software testing and/or dynamic analysis to detect. deadlocks. Their effectiveness is dependent on well-designed multithreaded test cases. Unsurprisingly, developing multithreaded tests is significantly harder than developing sequential tests for obvious reasons. In this paper, we address the problem of automatically synthesizing multithreaded tests that can induce deadlocks. The key insight to our approach is that a subset of the properties observed when a deadlock manifests in a concurrent execution can also be observed in a single threaded execution. We design a novel, automatic, scalable and directed approach that identifies these properties and synthesizes a deadlock revealing multithreaded test. The input to our approach is the library implementation under consideration and the output is a set of deadlock revealing multithreaded tests. We have implemented our approach as part of a tool, named OMEN1. OMEN is able to synthesize multithreaded tests on many multithreaded Java libraries. Applying a dynamic deadlock detector on the execution of the synthesized tests results in the detection of a number of deadlocks, including 35 real deadlocks in classes documented as thread-safe. Moreover, our experimental results show that dynamic analysis on multithreaded tests that are either synthesized randomly or developed by third-party programmers are ineffective in detecting the deadlocks.

Trace Driven Dynamic Deadlock Detection and Reproduction

Dynamic analysis techniques have been proposed to detect potential deadlocks. Analyzing and comprehending each potential deadlock to determine whether the deadlock is feasible in a real execution requires significant programmer effort. Moreover, empirical evidence shows that existing analyses are quite imprecise. This imprecision of the analyses further void the manual effort invested in reasoning about non-existent defects. In this paper, we address the problems of imprecision of existing analyses and the subsequent manual effort necessary to reason about deadlocks. We propose a novel approach for deadlock detection by designing a dynamic analysis that intelligently leverages execution traces. To reduce the manual effort, we replay the program by making the execution follow a schedule derived based on the observed trace. For a real deadlock, its feasibility is automatically verified if the replay causes the execution to deadlock. We have implemented our approach as part of WOLF and have analyzed many large (upto 160KLoC) Java programs. Our experimental results show that we are able to identify 74% of the reported defects as true (or false) positives automatically leaving very few defects for manual analysis. The overhead of our approach is negligible making it a compelling tool for practical adoption.

Homology and enzymatic requirements of microhomology-dependent alternative end joining

Nonhomologous DNA end joining (NHEJ) is one of the major double-strand break (DSB) repair pathways in higher eukaryotes. Recently, it has been shown that alternative NHEJ (A-NHEJ) occurs in the absence of classical NHEJ and is implicated in chromosomal translocations leading to cancer. In the present study, we have developed a novel biochemical assay system utilizing DSBs flanked by varying lengths of microhomology to study microhomology-mediated alternative end joining (MMEJ). We show that MMEJ can operate in normal cells, when microhomology is present, irrespective of occurrence of robust classical NHEJ. Length of the microhomology determines the efficiency of MMEJ, 5 nt being obligatory. Using this biochemical approach, we show that products obtained are due to MMEJ, which is dependent on MRE11, NBS1, LIGASE III, XRCC1, FEN1 and PARP1. Thus, we define the enzymatic machinery and microhomology requirements of alternative NHEJ using a well-defined biochemical system.

A Universal Stress Protein (USP) in Mycobacteria Binds cAMP

Mycobacteria are endowed with rich and diverse machinery for the synthesis, utilization, and degradation of cAMP. The actions of cyclic nucleotides are generally mediated by binding of cAMP to conserved and well characterized cyclic nucleotide binding domains or structurally distinct cGMP-specific and -regulated cyclic nucleotide phosphodiesterase, adenylyl cyclase, and E. coli transcription factor FhlA (GAF) domain-containing proteins. Proteins with cyclic nucleotide binding and GAF domains can be identified in the genome of mycobacterial species, and some of them have been characterized. Here, we show that a significant fraction of intracellular cAMP is bound to protein in mycobacterial species, and by using affinity chromatography techniques, we identify specific universal stress proteins (USP) as abundantly expressed cAMP-binding proteins in slow growing as well as fast growing mycobacteria. We have characterized the biochemical and thermodynamic parameters for binding of cAMP, and we show that these USPs bind cAMP with a higher affinity than ATP, an established ligand for other USPs. We determined the structure of the USP MSMEG_3811 bound to cAMP, and we confirmed through structure-guided mutagenesis, the residues important for cAMP binding. This family of USPs is conserved in all mycobacteria, and we suggest that they serve as ``sinks'' for cAMP, making this second messenger available for downstream effectors as and when ATP levels are altered in the cell.

Relay Selection with Channel Probing in Sleep-Wake Cycling Wireless Sensor Networks

In geographical forwarding of packets in a large wireless sensor network (WSN) with sleep-wake cycling nodes, we are interested in the local decision problem faced by a node that has ``custody'' of a packet and has to choose one among a set of next-hop relay nodes to forward the packet toward the sink. Each relay is associated with a ``reward'' that summarizes the benefit of forwarding the packet through that relay. We seek a solution to this local problem, the idea being that such a solution, if adopted by every node, could provide a reasonable heuristic for the end-to-end forwarding problem. Toward this end, we propose a local relay selection problem consisting of a forwarding node and a collection of relay nodes, with the relays waking up sequentially at random times. At each relay wake-up instant, the forwarder can choose to probe a relay to learn its reward value, based on which the forwarder can then decide whether to stop (and forward its packet to the chosen relay) or to continue to wait for further relays to wake up. The forwarder's objective is to select a relay so as to minimize a combination of waiting delay, reward, and probing cost. The local decision problem can be considered as a variant of the asset selling problem studied in the operations research literature. We formulate the local problem as a Markov decision process (MDP) and characterize the solution in terms of stopping sets and probing sets. We provide results illustrating the structure of the stopping sets, namely, the (lower bound) threshold and the stage independence properties. Regarding the probing sets, we make an interesting conjecture that these sets are characterized by upper bounds. Through simulation experiments, we provide valuable insights into the performance of the optimal local forwarding and its use as an end-to-end forwarding heuristic.

GBNV encoded movement protein (NSm) remodels ER network via C-terminal coiled coil domain

Plant viruses exploit the host machinery for targeting the viral genome-movement protein complex to plasmodesmata (PD). The mechanism by which the non-structural protein m (NSm) of Groundnut bud necrosis virus (GBNV) is targeted to PD was investigated using Agrobacterium mediated transient expression of NSm and its fusion proteins in Nicotiana benthamiana. GFP:NSm formed punctuate structures that colocalized with mCherry:plasmodesmata localized protein la (PDLP la) confirming that GBNV NSm localizes to PD. Unlike in other movement proteins, the C-terminal coiled coil domain of GBNV NSm was shown to be involved in the localization of NSm to PD, as deletion of this domain resulted in the cytoplasmic localization of NSm. Treatment with Brefeldin A demonstrated the role of ER in targeting GFP NSm to PD. Furthermore, mCherry:NSm co-localized with ER-GFP (endoplasmic reticulum targeting peptide (HDEL peptide fused with GFP). Co-expression of NSm with ER-GFP showed that the ER-network was transformed into vesicles indicating that NSm interacts with ER and remodels it. Mutations in the conserved hydrophobic region of NSm (residues 130-138) did not abolish the formation of vesicles. Additionally, the conserved prolines at positions 140 and 142 were found to be essential for targeting the vesicles to the cell membrane. Further, systematic deletion of amino acid residues from N- and C-terminus demonstrated that N-terminal 203 amino acids are dispensable for the vesicle formation. On the other hand, the C-terminal coiled coil domain when expressed alone could also form vesicles. These results suggest that GBNV NSm remodels the ER network by forming vesicles via its interaction through the C-terminal coiled coil domain. Interestingly, NSm interacts with NP in vitro and coexpression of these two proteins in planta resulted in the relocalization of NP to PD and this relocalization was abolished when the N-terminal unfolded region of NSm was deleted. Thus, the NSm interacts with NP via its N-terminal unfolded region and the NSm-NP complex could in turn interact with the ER membrane via the C-terminal coiled coil domain of NSm to form vesicles that are targeted to PD and there by assist the cell to cell movement of the viral genome complex. (C) 2015 Elsevier Inc. All rights reserved.

An Optimizing Code Generator for a Class of Lattice-Boltzmann Computations

The Lattice-Boltzmann method (LBM), a promising new particle-based simulation technique for complex and multiscale fluid flows, has seen tremendous adoption in recent years in computational fluid dynamics. Even with a state-of-the-art LBM solver such as Palabos, a user has to still manually write the program using library-supplied primitives. We propose an automated code generator for a class of LBM computations with the objective to achieve high performance on modern architectures. Few studies have looked at time tiling for LBM codes. We exploit a key similarity between stencils and LBM to enable polyhedral optimizations and in turn time tiling for LBM. We also characterize the performance of LBM with the Roofline performance model. Experimental results for standard LBM simulations like Lid Driven Cavity, Flow Past Cylinder, and Poiseuille Flow show that our scheme consistently outperforms Palabos-on average by up to 3x while running on 16 cores of an Intel Xeon (Sandybridge). We also obtain an improvement of 2.47x on the SPEC LBM benchmark.

Bioengineering of AAV2 Capsid at Specific Serine, Threonine, or Lysine Residues Improves Its Transduction Efficiency in Vitro and in Vivo

We hypothesized that the AAV2 vector is targeted for destruction in the cytoplasm by the host cellular kinase/ubiquitination/proteasomal machinery and that modification of their targets on AAV2 capsid may improve its transduction efficiency. In vitro analysis with pharmacological inhibitors of cellular serine/threonine kinases (protein kinase A, protein kinase C, casein kinase II) showed an increase (20-90%) on AAV2-mediated gene expression. The three-dimensional structure of AAV2 capsid was then analyzed to predict the sites of ubiquitination and phosphorylation. Three phosphodegrons, which are the phosphorylation sites recognized as degradation signals by ubiquitin ligases, were identified. Mutation targets comprising eight serine (S) or seven threonine (T) or nine lysine (K) residues were selected in and around phosphodegrons on the basis of their solvent accessibility, overlap with the receptor binding regions, overlap with interaction interfaces of capsid proteins, and their evolutionary conservation across AAV serotypes. AAV2-EGFP vectors with the wild-type (WT) capsid or mutant capsids (15 S/T -> alanine A] or 9 K -> arginine R] single mutant or 2 double K -> R mutants) were then evaluated in vitro. The transduction efficiencies of 11 S/T -> A and 7 K -> R vectors were significantly higher (similar to 63-90%) than the AAV2-WT vectors (similar to 30-40%). Further, hepatic gene transfer of these mutant vectors in vivo resulted in higher vector copy numbers (up to 4.9-fold) and transgene expression (up to 14-fold) than observed from the AAV2-WT vector. One of the mutant vectors, S489A, generated similar to 8-fold fewer antibodies that could be cross-neutralized by AAV2-WT. This study thus demonstrates the feasibility of the use of these novel AAV2 capsid mutant vectors in hepatic gene therapy.

Targeted Modifications in Adeno-Associated Virus Serotype 8 Capsid Improves Its Hepatic Gene Transfer Efficiency In Vivo

Recombinant adeno-associated virus vectors based on serotype 8 (AAV8) have shown significant promise for liver-directed gene therapy. However, to overcome the vector dose dependent immunotoxicity seen with AAV8 vectors, it is important to develop better AAV8 vectors that provide enhanced gene expression at significantly low vector doses. Since it is known that AAV vectors during intracellular trafficking are targeted for destruction in the cytoplasm by the host-cellular kinase/ubiquitination/proteasomal machinery, we modified specific serine/threonine kinase or ubiquitination targets on the AAV8 capsid to augment its transduction efficiency. Point mutations at specific serine (S)/threonine (T)/lysine (K) residues were introduced in the AAV8 capsid at the positions equivalent to that of the effective AAV2 mutants, generated successfully earlier. Extensive structure analysis was carried out subsequently to evaluate the structural equivalence between the two serotypes. scAAV8 vectors with the wild-type (WT) and each one of the S/T -> Alanine (A) or K-Arginine (R) mutant capsids were evaluated for their liver transduction efficiency in C57BL/6 mice in vivo. Two of the AAV8-S -> A mutants (S279A and S671A), and a K137R mutant vector, demonstrated significantly higher enhanced green fluorescent protein (EGFP) transcript levels (similar to 9- to 46-fold) in the liver compared to animals that received WT-AAV8 vectors alone. The best performing AAV8 mutant (K137R) vector also had significantly reduced ubiquitination of the viral capsid, reduced activation of markers of innate immune response, and a concomitant two-fold reduction in the levels of neutralizing antibody formation in comparison to WT-AAV8 vectors. Vector bio-distribution studies revealed that the K137R mutant had a significantly higher and preferential transduction of the liver (106 vs. 7.7 vector copies/mouse diploid genome) when compared to WT-AAV8 vectors. To further study the utility of the K137R-AAV8 mutant in therapeutic gene transfer, we delivered human coagulation factor IX (h. FIX) under the control of liver-specific promoters (LP1 or hAAT) into C57BL/6 mice. The circulating levels of h. FIX: Ag were higher in all the K137R-AAV8 treated groups up to 8 weeks post-hepatic gene transfer. These studies demonstrate the feasibility of the use of this novel AAV8 vectors for potential gene therapy of hemophilia B.

Crystallographic studies of the extracytoplasmic function sigma factor sigma(J) from Mycobacterium tuberculosis

Mycobacterium tuberculosis has multiple sigma factors which enable the bacterium to reprogram its transcriptional machinery under diverse environmental conditions. sigma(J), an extracytoplasmic function sigma factor, is upregulated in late stationary phase cultures and during human macrophage infection. sigma(J) governs the cellular response to hydrogen peroxide-mediated oxidative stress. sigma(J) differs from other canonical sigma factors owing to the presence of a SnoaL_2 domain at the C-terminus. sigma(J) crystals belonged to the tetragonal space group I422, with unit-cell parameters a = b = 133.85, c = 75.08 angstrom. Diffraction data were collected to 2.16 angstrom resolution on the BM14 beamline at the European Synchrotron Radiation Facility (ESRF).

Is the cellular initiation of translation an exclusive property of the initiator tRNAs?

Translation of mRNAs is the primary function of the ribosomal machinery. Although cells allow for a certain level of translational errors/mistranslation (which may well be a strategic need), maintenance of the fidelity of translation is vital for the cellular function and fitness. The P-site bound initiator tRNA selects the start codon in an mRNA and specifies the reading frame. A direct P-site binding of the initiator tRNA is a function of its special structural features, ribosomal elements, and the initiation factors. A highly conserved feature of the 3 consecutive G:C base pairs (3GC pairs) in the anticodon stem of the initiator tRNAs is vital in directing it to the P-site. Mutations in the 3GC pairs diminish/abolish initiation under normal physiological conditions. Using molecular genetics approaches, we have identified conditions that allow initiation with the mutant tRNAs in Escherichia coli. During our studies, we have uncovered a novel phenomenon of in vivo initiation by elongator tRNAs. Here, we recapitulate how the cellular abundance of the initiator tRNA, and nucleoside modifications in rRNA are connected with the tRNA selection in the P-site. We then discuss our recent finding of how a conserved feature in the mRNA, the Shine-Dalgarno sequence, influences tRNA selection in the P-site.

Multiobjective fuzzy optimization for sustainable groundwater management using particle swarm optimization and analytic element method

Groundwater management involves conflicting objectives as maximization of discharge contradicts the criteria of minimum pumping cost and minimum piping cost. In addition, available data contains uncertainties such as market fluctuations, variations in water levels of wells and variations of ground water policies. A fuzzy model is to be evolved to tackle the uncertainties, and a multiobjective optimization is to be conducted to simultaneously satisfy the contradicting objectives. Towards this end, a multiobjective fuzzy optimization model is evolved. To get at the upper and lower bounds of the individual objectives, particle Swarm optimization (PSO) is adopted. The analytic element method (AEM) is employed to obtain the operating potentio metric head. In this study, a multiobjective fuzzy optimization model considering three conflicting objectives is developed using PSO and AEM methods for obtaining a sustainable groundwater management policy. The developed model is applied to a case study, and it is demonstrated that the compromise solution satisfies all the objectives with adequate levels of satisfaction. Sensitivity analysis is carried out by varying the parameters, and it is shown that the effect of any such variation is quite significant. Copyright (c) 2015 John Wiley & Sons, Ltd.

Characterization of Precursor PfHsp60 in Plasmodium falciparum Cytosol during Its Asexual Development in Human Erythrocytes

Mitochondrial heat shock protein 60 (Hsp60) is a nuclear encoded gene product that gets post-translationally translocated into the mitochondria. Using multiple approaches such as immunofluorescence experiments, isoelectric point analysis with two-dimensional gel electrophoresis, and mass spectrometric identification of the signal peptide, we show that Hsp60 from Plasmodium falciparum (PfHsp60) accumulates in the parasite cytoplasm during the ring, trophozoite, and schizont stages of parasite development before being imported into the parasite mitochondria. Using co-immunoprecipitation experiments with antibodies specific to cytoplasmic PfHsp90, PfHsp70-1, and PfHsp60, we show association of precursor PfHsp60 with cytoplasmic chaperone machinery. Metabolic labeling involving pulse and chase indicates translocation of the precursor pool into the parasite mitochondrion during chase. Analysis of results obtained with Geldanamycin treatment confirmed precursor PfHsp60 to be one of the clients for PfHsp90. Cytosolic chaperones bind precursor PfHsp60 prior to its import into the mitochondrion of the parasite. Our data suggests an inefficient co-ordination in the synthesis and translocation of mitochondrial PfHsp60 during asexual growth of malaria parasite in human erythrocytes.

Synthesizing Racy Tests

Subtle concurrency errors in multithreaded libraries that arise because of incorrect or inadequate synchronization are often difficult to pinpoint precisely using only static techniques. On the other hand, the effectiveness of dynamic race detectors is critically dependent on multithreaded test suites whose execution can be used to identify and trigger races. Usually, such multithreaded tests need to invoke a specific combination of methods with objects involved in the invocations being shared appropriately to expose a race. Without a priori knowledge of the race, construction of such tests can be challenging. In this paper, we present a lightweight and scalable technique for synthesizing precisely these kinds of tests. Given a multithreaded library and a sequential test suite, we describe a fully automated analysis that examines sequential execution traces, and produces as its output a concurrent client program that drives shared objects via library method calls to states conducive for triggering a race. Experimental results on a variety of well-tested Java libraries yield 101 synthesized multithreaded tests in less than four minutes. Analyzing the execution of these tests using an off-the-shelf race detector reveals 187 harmful races, including several previously unreported ones.

Coupling geomorphology parameters with lithology for micro-level groundwater resource assessment: a case study from semi-arid hard rock terrain in Tamil Nadu, India

The standard procedure of groundwater resource estimation in India till date is based on the specific yield parameters of each rock type (lithology) derived through pumping test analysis. Using the change in groundwater level, specific yield, and area of influence, groundwater storage change could be estimated. However, terrain conditions in the form of geomorphological variations have an important bearing on the net groundwater recharge. In this study, an attempt was made to use both lithology and geomorphology as input variables to estimate the recharge from different sources in each lithology unit influenced by the geomorphic conditions (lith-geom), season wise separately. The study provided a methodological approach for an evaluation of groundwater in a semi-arid hard rock terrain in Tirunelveli, Tamil Nadu, India. While characterizing the gneissic rock, it was found that the geomorphologic variations in the gneissic rock due to weathering and deposition behaved differently with respect to aquifer recharge. The three different geomorphic units identified in gneissic rock (pediplain shallow weathered (PPS), pediplain moderate weathered (PPM), and buried pediplain moderate (BPM)) showed a significant variation in recharge conditions among themselves. It was found from the study that Peninsular gneiss gives a net recharge value of 0.13 m/year/unit area when considered as a single unit w.r.t. lithology, whereas the same area considered with lith-geom classes gives recharge values between 0.1 and 0.41 m/year presenting a different assessment. It is also found from this study that the stage of development (SOD) for each lith-geom unit in Peninsular gneiss varies from 168 to 230 %, whereas the SOD is 223 % for the lithology as a single unit.