Department of Computer Science and Automation Department of Computer Science and Automation, IISc, Bangalore, India Indian Institute of Science
HOME | ABOUT US | PEOPLE | RESEARCH | ACADEMICS | FACILITIES | EVENTS / SEMINARS | NEWS | CONTACT US

UPCOMING SEMINARS

Series: Research Student Colloquium
Title: 1. ​A brief introduction to Arithmetic circuit complexity 2. ​Prudent Memory Reclamation in Procrastination-Based Synchronization

  • Speaker: 1. Mr. Nikhil Gupta
                   2. Mr. Aravinda Prasad
  • Date and Time: Friday, February 23, 2018, 4:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
1. Arithmetic circuit complexity theory deals with computation of multivariate polynomials over a field F using addition (+) and multiplication (*) operations. One of the computation model that captures this computation is arithmetic circuits, with the size of circuit as an associated measure. An interesting question is, given a polynomial, to find tight lower bounds on the size of arithmetic circuits computing it. This is important, because a super-polynomial lower bound on the size of arithmetic circuits computing the ‘symbolic permanent’ would give a separation between VP and VNP (algebraic analogues of P and NP respectively). There are several ways to prove lower bounds. One of the approaches is the complexity measure approach, in which a complexity measure like ‘evaluation dimension’, ‘rank of partial derivative matrix’ etc is chosen to give lower bounds. In this talk, I will give a skeleton to prove lower bounds using the complexity measure and state some well-known results. Another important problem in this area is to give a deterministic polynomial time algorithm to test, if a given arithmetic circuit computes the zero polynomial (PIT). An efficient randomized algorithm is known for PIT due to Schwartz-Zippel lemma, but derandomizing this is a long standing open problem. This is important from the perspective of complexity theory because an efficient deterministic PIT would either give a super-polynomial lower bound on the size of circuits computing the ‘symbolic permanent’ or show that the problems in the boolean complexity class NEXP can’t be computed by polynomial size boolean circuits.

2. Procrastination is the fundamental technique used in synchronization mechanisms such as Read-Copy-Update (RCU) where writers, in order to synchronize with readers, defer the freeing of an object until there are no readers referring to the object. The synchronization mechanism determines when the deferred object is safe to reclaim and when it is actually reclaimed. Hence, such memory reclamations are completely oblivious of the memory allocator state. This induces poor memory allocator performance, for instance, when the reclamations are ill-timed. Furthermore, deferred objects provide hints about the future that inform memory regions that are about to be freed. Although useful, hints are not exploited as deferred objects are not "visible" to memory allocators. We introduce Prudence, a dynamic memory allocator, that is tightly integrated with the synchronization mechanism to ensure visibility of deferred objects to the memory allocator. Such an integration enables Prudence to (i) identify the safe time to reclaim deferred objects' memory, (ii) have an inclusive view of the allocated, free and about-to-be-freed objects, and (iii) exploit optimizations based on the hints about the future during important state transitions. Our evaluation in the Linux kernel shows that Prudence integrated with RCU performs 3.9x to 28x better in microbenchmarks compared to SLUB, a recent memory allocator in the Linux kernel. It also improves the overall performance perceptibly (4%-18%) for a mix of widely used synthetic and application benchmarks. Further, it performs better (up to 98%) in terms of object hits in caches, object cache churns, slab churns, peak memory usage and total fragmentation, when compared with the SLUB allocator.

Speaker Bio:
1. Nikhil Gupta is a first year Ph.D. student at the department of CSA under prof. Chandan Saha. He works in the area of algebraic complexity theory. Relevant lab(s): theoretical Computer Science 2. Aravinda Prasad is a PhD (ERP) student, where he is advised by Prof. K Gopinath and Dr. Vinayaka D Pandit (IBM). Relevant lab(s): Computer Systems and Software

Host Faculty: Prof. Sunil Chandran & Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: An Introduction to Well-Structured Transition Systems

  • Speaker: Alain Finkel
  • Date and Time: Wednesday, February 21, 2018, 3:30 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Well-Structured Transition Systems (WSTS) are a general class of infinite state systems, which allow a certain ordering on states that is compatible with the transition relation of the system. Many verification problems turn out to be decidable for this general class of systems. In particular, the theory of WSTS yields decidability results for important classes of system models like Petri Nets and Lossy Channel Systems.

In this talk we will present the concepts, the story, some WSTS models, some applications to different questions, and the main decidability results for WSTS.

Speaker Bio:
Alain Finkel is a professor at the Ecole Normale Superieure, Cachan, and a member of the Laboratory for Specification and Verification at ENS Cachan. He is well-known for his work on verification of infinite state systems. He is a recipient of the CAV award in 2017 for his work on WSTS.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Data Analytics – Opportunities and Responsibilities

  • Speaker: Prof. Venkat V.S.S.Sastry
                   Head
                   Royal Military College of Science
                   Shrivenham
                   United Kingdom
  • Date and Time: Wednesday, February 21, 2018, 2:15 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
With rapid developments in computing power, phenomenal rate at which data being generated a second, there are numerous opportunities to exploit the data for the benefit to all concerned – design better products and deliver what is needed just in time. The sheer size of data available that cannot fit into a computer’s memory requires new ways of analysing the data, and new algorithms. Patterns in the data can reveal inherent relationships and also expose anomalous events. These opportunities do come with attendant challenges and raises many ethical questions too.

Data analysis is becoming increasingly multi-disciplinary in nature and requires sound technical skills as well as good communication skills. When dealing with data, the scientist is often confronted with ethical considerations that need to be addressed right up front. Access to data alone is not sufficient to justify further analysis as the results may have far-reaching implications. This is particularly relevant when working with data in cyberspace.

The talk provides an overview of some of the applications that are being pursued here at Cranfield University. These range from digital forensics, forensic investigations, cybersecurity, learning/learner analytics and vehicle health monitoring. The level of technical details are kept to a minimum to make the talk accessible to public. The younger generation should find the examples sufficiently motivating to take up the discipline.

Speaker Bio:
Dr. Venkat V S S Sastry obtained his PhD in applied mathematics from Indian Institute of Science, Bangalore (1980). After a brief period as Research assistant at IISc, Bangalore working on Helicopter Dynamics, he moved to Open University, Milton Keynes where he worked as postdoctoral research fellow (1981 - 1984) on acoustic wave propagation over rigid-porous media and acoustic-to-seismic coupling in poro-elastic media. He continued his interests in acoustic wave propagation at Plymouth Polytechnic (1984 - 1987) as Research Fellow working on scattering of acoustic waves by fluid-loaded elastic objects. He subsequently joined Department of Mathematics and Statistics, as Lecturer at Plymouth Polytechnic (1987 - 1989). In November 1989, Dr. Sastry joined Department of Applied Mathematics and Operational Research, the then Royal Military College of Science, Shrivenham where he continues as Head of Applied Mathematics and Scientific Computing (2003 - ), Centre for Simulation and Analytics, Shrivenham where he continues as Head of Applied Mathematics and Scientific Computing (2003 - ), Centre for Simulation and Analytics, School of Cranfield Defence and Security. He is currently Programme Director for Chevening Cyber Security Fellowship (2014 - ). Dr. Sastry is the principal investigator on an ASTRAEA 2 project "Sense and Avoid" (BAESYSTEMS) and principal investigator on "What to do Learners within an m-Learning Environment Need?", (ONRG Grant N62909-10-1-7121) and is Co-Chair on Working Group for Testing and Evaluation, Mobile Learning Environments Project. He is winner of The Engineer, Technology + innovation awards 2008 for best collaborative research team, BAE Systems, Cranfield and Lancaster Universities for work on conflict avoidance and resolution algorithms for unmanned aerial vehicles. Dr. Sastry is passionate about e-Assessment and measurement of performance in academic setting; and has been administering diagnostic tests using bespoke software developed at Cranfield University since 2002. He has been organising a two day conference on E-Assessment in Practice since 2008. Since 2012 he joined CAA Programme Committee as e-Assessment in Practice Chair.

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

PAST SEMINARS

Series: Ph.D. Thesis Defense
Title: Falcon : A Graph Manipulation Language for Distributed Heterogeneous Systems

  • Speaker: Unnikrishnan C
  • Faculty Advisor: Y.N. Srikant
  • Date and Time: Monday, February 19, 2018, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Graphs model relationships across real-world entities in web graphs, social network graphs, and road network graphs. Graph algorithms analyze and transform a graph to discover graph properties or to apply a computation. For instance, a pagerank algorithm computes a rank for each page in a webgraph, and a community detection algorithm discovers likely communities in a social network, while a shortest path algorithm computes the quickest way to reach a place from another, in a road network. In Domains such as social information systems, the number of edges can be in billions or trillions. Such large graphs are processed on distributed computer systems or clusters.

Graph algorithms can be executed on multi-core CPUs, GPUs with thousands of cores, multi-GPU devices, and CPU+GPU clusters, depending on the size of the graph object. While programming such algorithms on heterogeneous targets, a programmer is required to deal with parallelism and and also manage explicit data communication between distributed devices. This implies that a programmer is required to learn CUDA, OpenMP, MPI, etc., and also the details of the hardware architecture. Such codes are error prone and difficult to debug. A Domain Specific Language (DSL) which hides all the hardware details and lets the programmer concentrate only the algorithmic logic will be very useful.

With this as the research goal, Falcon, a graph DSL, and its compiler have been developed. Falcon programs are explicitly parallel and Falcon hides all the hardware details from the programmer. Large graphs that do not fit into the memory of a single device are automatically partitioned by the Falcon compiler. Another feature of Falcon is that it supports mutation of graph objects and thus enables programming dynamic graph algorithms. The Falcon compiler converts a single DSL code to heterogeneous targets such as multi-core CPUs, GPUs, multi-GPU devices, and CPU+GPU clusters. Compiled codes of Falcon match or outperform state-of-the-art graph frameworks for different target platforms and benchmarks.

Speaker Bio:
Mr.Unnikrishnan is a Ph.D student of the CSA department and is currently pursuing his post-doc research in Singapore.

Host Faculty: Y.N. Srikant

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: On the Complexity of Training a Neural Network

  • Speaker: Prof. Santosh Vempala
                   Frederick Storey chair
                   and Distinguished Professor of Computer Science
                   Georgia Tech
                   Atlanta
  • Date and Time: Friday, February 16, 2018, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The empirical successes of deep learning currently lack rigorous explanation and the effectiveness of gradient descent in particular has mostly been a mystery. As a first step, we focus on training neural networks with a single hidden layer of unbiased activation units and find a surprisingly general polynomial-time analysis of gradient descent, exploiting new connections with tools from spherical harmonics. On the other hand, when the target function is generated by a network using arbitrary biases, the problem is intractable. We construct a family of simple neural networks with a single hidden layer, smooth activation functions and benign input distributions that is hard to learn in the sense that any statistical query algorithm (including all known variants of stochastic gradient descent with any loss function, for any model architecture) needs an exponential number of queries. In describing these results, we will discuss several open problems.

Speaker Bio:
Santosh Vempala is Frederick Storey chair and Distinguished Professor of Computer Science at Georgia Tech, where he served as the founding director of the Algorithms and Randomness Center (2006--2011). Vempala's research interests are broadly in the theory of algorithms, including algorithmic tools for sampling, learning, optimization and data analysis; high-dimensional geometry; randomized linear algebra; and Computing-for-Good (C4G). He graduated from CMU in 1997 advised by Avrim Blum and then taught at MIT until 2006 except for a year as a Miller Fellow at UC Berkeley. Vempala is also a Sloan, Guggenheim, ACM and generally excitable Fellow, especially when a phenomenon that appears complex from one perspective, turns out to be simple from another. In recent years, he has been trying to understand how to model the computational abilities of the brain.

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Data Structures and Algorithms to Analyze Concurrency in Android Applications

  • Speaker: Ms. Pallavi Maiya H P
                   PhD Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Aditya S Kanade
  • Date and Time: Friday, February 16, 2018, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Android is a popular mobile operating system, providing a rich ecosystem for the development of applications which run on the Android platform. Entities such as the device user, network and sensors interact continuously with the mobile device causing an Android application to face a continuous stream of input (events). In spite of having to perpetually handle a huge volume of events, Android applications are expected to be responsive to new events from the environment. The Android framework achieves this by exposing applications to a concurrency model which combines multi-threading with asynchronous event-based dispatch. While this enables development of efficient applications, unforeseen thread interleavings combined with non-deterministic ordering of events can lead to subtle concurrency bugs in Android applications.

In an Android application, threads communicate through shared variables and by sending events to each other's event queues. Even though typically a thread processes events in its event queue and invokes corresponding event handlers in a FIFO order, this ordering however can be altered by attributes such as delays and priorities associated with the events. The existing literature extensively describes techniques to detect concurrency bugs such as data races, deadlocks and atomicity violations in multi-threaded programs. Recent works also present techniques to analyze bugs manifested due to single-threaded event-driven concurrency. However, the complex event-driven semantics of Android applications combined with the thread-based semantics render a naive extension of such concurrency analysis techniques either less effective or unsound for Android applications. This thesis takes the initial steps towards developing data structures and algorithms to facilitate effective dynamic concurrency analysis of Android applications.

We firstly formalize the concurrency behaviour of Android applications by giving concurrency semantics. Using this semantics we derive a set of rules to reason about the happens-before ordering between operations in an Android execution trace. These rules induce a partial order called a happens-before (HB) relation on the operations of an execution trace. Our HB relation generalizes the so far independently studied HB relations for multi-threaded programs and single-threaded event-driven programs. We have developed a happens-before based dynamic race detector for Android applications, called DroidRacer, which detects data races across threads as well as race conditions between memory accesses from different event handlers on the same thread. DroidRacer has detected several races in various Android applications.

We identify a major bottleneck in the computation of the HB relation for Android applications, that of discovering HB order between event handlers executed on the same thread. HB order between events in Android is characterized by complex HB rules which order a pair of event handlers by inspecting, for example, the order between operations which enqueued the corresponding events. Android applications usually receive a large number of events even within a short span of time, which increases the cost of evaluating such HB rules. As a result HB computation using standard data structures such as vector clocks alone becomes inefficient in case of Android applications. We propose a novel data structure, called "event graph", that maintains a subset of the HB relation to efficiently infer order between any pair of events. We present an algorithm, called EventTrack, which improves efficiency of vector clock based HB computation for event-driven programs using event graphs. Evaluation of EventTrack against a state-of-the-art HB computation technique for Android applications, yielded significant speedup.

The scope of the happens-before based dynamic race detector is limited to the thread interleaving corresponding to the execution trace inspected. However, a systematic state space exploration technique such as a stateless model checker can explore all the thread interleavings, and also identify harmful manifestations of data races which may happen only when multiple racing memory accesses are performed in a particular order. Partial order reduction (POR) is a technique used by stateless model checkers to reduce the state space to be explored while preserving certain interesting program properties. The existing POR techniques selectively explore different thread interleavings only to reorder pairs of racing operations from different threads. However, they fail to follow this strategy for events and hence end up eagerly exploring all possible ordering between event handlers executed on the same thread, even if reordering them does not lead to different states. We propose a new POR technique based on a novel backtracking set called the "dependence-covering set". Events handled by the same thread are reordered by our POR technique only if necessary. We prove that exploring dependence-covering sets suffices to detect all deadlock cycles and assertion violations. To evaluate effectiveness of our POR scheme, we have implemented a dynamic algorithm to compute dependence-covering sets. On execution traces obtained from a few Android applications, we demonstrate that our technique explores many fewer transitions —often orders of magnitude fewer— compared to exploration based on persistent sets, a popular POR technique which explores all possible orderings between events. The tools, (i) Droidracer, a race detector for Android applications, (ii) a standalone implementation of EventTrack, to compute HB relation over Android execution traces, and (iii) EM-Explorer --- a proof-of-concept model checking framework which simulates the non-deterministic behaviour exhibited by Android applications, developed by this thesis have been made public.

Video Archive Go Top

 

Series: Department Seminar
Title: Understanding Indian Climate through a spatio-temporally coherent Random Field

  • Speaker: Dr. Adway Mitra
                   Postdoctoral Fellow
                   International Center for Theoretical Sciences (ICTS-TIFR)
                   Bangalore
  • Date and Time: Thursday, February 15, 2018, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Climatic conditions have a profound impact on the lives of a billion people in India. However, several questions related to Indian climate are still unanswered to climate scientists. The widespread availability of high-quality climatic data along with advances in Data Science and Machine Learning have opened up scope for a data-driven approach to these problems. Climatic data is spatio-temporal in nature, where each climatic variable (temperature, rainfall, wind speed etc) is measured at different locations and time-points. Climatic processes can occur at different spatial and temporal scales, but usually each process spans many spatial and temporal locations. We build a spatio-temporal model based on Markov Random Field, where climatic processes are encoded by discrete latent variables and spatio-temporal coherence maintained through edge potential functions. This model is used as the basis of our approach to three problems – detection of large-scale anomaly events, daily rainfall simulation and understanding spatio-temporal dynamics of Indian Monsoon.

A slight deviation (anomaly) from normal conditions (climatology) can have severe impacts. In India, the most significant impacts are caused by excess/deficient rainfall and excess temperature. The most significant anomalies are those that extend over a large area and/or persist for a long time, which we call “anomaly events”. Detection and localizing such events in space and time is a challenge, and we try to address it using our proposed models. The model also allows us to estimate several statistical properties at local and regional scale, which are in turn used as inputs to stochastic models to simulate daily climatic conditions across India. We show that our simulations reflect spatio-temporal properties of the process much more accurately than simulations done by dynamical models used by climate scientists. We also identify homogeneous zones across the landmass, within which rainfall simulation may be carried out more accurately. Additionally, we use our framework to identify common spatial and temporal patterns of rainfall over India during monsoon season, which provide important insights into the dynamics of this highly complex phenomena, and creates some scope for rainfall prediction at local and regional scale.

Speaker Bio:
Adway Mitra is currently a postdoctoral fellow in International Center for Theoretical Sciences (ICTS-TIFR) in Bangalore. He received his Ph.D. from Indian Institute of Science in 2016, under the guidance of Prof. Chiranjib Bhattacharyya. Prior to that he received M.E. from IISc in 2010, and B.E. from Jadavpur University in 2008. His primary research interest is in modeling complex spatio-temporal processes, especially climate, using Statistics, Data Mining and Machine Learning.

Host Faculty: Prof. Chiranjib Bhattacharyya

Video Archive Go Top

 

Series: Faculty Colloquium
Title: On statistical analysis of spectral graph algorithms for community detection in networks

  • Speaker: Prof. Ambedkar Dukkipati
                   Associate Professor
                   Dept. of CSA
  • Date and Time: Friday, February 09, 2018, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In the last few decades, we have witnessed a massive explosion of network or relational data: from social to biological networks. One of the most important problems in network analysis is community detection in networks. Communities or clusters of highly connected actors form an essential feature in the structure of several real-world networks. Spectral graph methods for detecting communities in networks have been very successful for two reasons: (i) good practical solutions and easy implementations, and (ii) theoretical guarantees. A statistical treatment for analysis of spectral algorithms involves, assuming that the data or network is generated from a random model, with a planted partition and then derive bounds on the error obtained by a particular spectral algorithm. A spectral algorithm is said to be strongly consistent if the error obtained is o(1) with high probability and weakly consistent if error obtained is o(n), where n is the number of nodes in a network.

While we think of networks that capture two-way interactions (edge size 2), there are other complex networks that can have multi-way interactions which are called hypergraphs. I will provide a brief account of our results on the consistency of hypergraph partitioning using spectral graph methods by giving details on required tools of the trade: Davis-Kahan theorems and some concentration inequalities. I will also provide a necessary background in the beginning of the talk by giving a quick introduction to spectral graph theory results that lead to an approximate method for graph partitioning.

Speaker Bio:
Ambedkar Dukkipati received B.tech from IIT Madras in Computer Science and Engineering, and Masters and PhD from Indian Institute of Science. After his postdoctoral research at EURANDOM in Eindhoven, he joined as a faculty at Computer Science and Automation (CSA), Indian Institute of Science. At present, he is the convener Statistics and Machine Learning Group at CSA and his research interests are in machine learning, statistical network analysis, deep learning and computational algebra.

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Heterogeneity Aware Shared DRAM Cache for Integrated Heterogeneous Architectures

  • Speaker: Adarsh Patil
  • Faculty Advisor: R. Govindarajan
  • Date and Time: Tuesday, February 06, 2018, 10:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Integrated Heterogeneous System (IHS) processors pack throughput-oriented GPGPUs along- side latency-oriented CPUs on the same die sharing certain resources, e.g., shared last level cache, network-on-chip (NoC), and the main memory. They also share virtual and physical address spaces and unify the memory hierarchy. The IHS architecture allows for easier programmability, data management and efficiency. However, the significant disparity in the demands for memory and other shared resources between the GPU cores and CPU cores poses significant problems in exploiting the full potential of this architecture.

In this work, we propose adding a large capacity stacked DRAM, used as a shared last level cache, for the IHS processors. The reduced latency of access and large bandwidth provided by the DRAM cache can help improve performance respectively of CPU and GPGPU while the large capacity can help contain the working set of the IHS workloads. However, adding the DRAM cache naively leaves significant performance on the table due to the disparate demands from CPU and GPU cores for DRAM cache and memory accesses. In particular, the imbalance can significantly reduce the performance benefits that the CPU cores would have otherwise enjoyed with the introduction of the DRAM cache. This necessitates a heterogeneity-aware management of this shared resource for improved performance. To address this, in this thesis, we propose three simple techniques to enhance the performance of CPU application while ensuring very little or no performance impact to the GPU. Specifically, we propose (i) PrIS, a prioritization scheme for scheduling CPU requests at the DRAM cache controller, (ii) ByE, a selective and temporal bypassing scheme for CPU requests at the DRAM cache and (iii) Chaining, an occupancy controlling mechanism for GPU lines in the DRAM cache through pseudo-associativity. The resulting cache HAShCache, is heterogeneity-aware and can adapt dynamically to address the inherent disparity of demands in an IHS architecture with simple light weight schemes.

We enhance the gem5-gpu simulator to model an IHS architecture with stacked DRAM as a cache, coherent GPU L2 cache and CPU caches and a shared unified physical memory. Using this setup we perform detailed experimental evaluation of the proposed HAShCache and demonstrate an average system performance (combined performance of CPU and GPU cores) improvement of 41% over a naive DRAM cache and over 100% improvement over a baseline system with no stacked DRAM cache.

Host Faculty: R. Govindarajan

Video Archive Go Top

 

Series: Department Seminar
Title: Containers: the minions of the cloud era

  • Speaker: Thejas CR
  • Date and Time: Monday, February 05, 2018, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
If one thinks of game changing technological revolutions of the last decade, containers certainly rank among the top few along with perhaps Cloud computing, AI/ML and Blockchain. Pretty much all Google services run in containers (https://cloud.google.com/containers/). The rate at which they have been adopted into production IT infrastructure by most of the Fortune 500 companies has been mind boggling (https://www.datadoghq.com/docker-adoption/). Container frameworks provide a lightweight, isolated, standardized packaging and runtime infrastructure to run diverse types of software services on physical servers. Their nimble nature enable them to become fungible entities and hence have changed the way services are composed and deployed on the cloud and the enterprise. Their wide adoption has also led to huge interest and investments in container orchestration software like Kubernetes. The foundations of containers lies in operating systems concepts like namespaces and cgroups. This talk is intended to give an overview of the building blocks of container technology, some practical applications, and future directions.

Speaker Bio:
Thejas CR is an alumnus of CSA, and is currently working as a software engineer at Arista Networks - a cloud networking company. He has more than a decade of industry experience in working on high-performance software systems, especially in the areas of computer networks and software infrastructure. At Arista he leads the tools and infrastructure team in Bangalore which is responsible for solving software scale problems facing the company as it grows from few tens to few thousand engineers. At CSA, Thejas was a Masters student advised by Prof. Uday Kumar Reddy B at the Multicore computing lab, where he worked on automatic memory allocation techniques for GPGPUs.

Host Faculty: Uday Kumar Reddy B

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Computing Contour Trees for 2D Piecewise Polynomial Functions

  • Speaker: Mr. Girijanandan Nucha
                   M.Sc. (Engg) student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Vijay Natarajan
  • Date and Time: Thursday, February 01, 2018, 9:30 AM
  • Venue: CSA Faculty Room, (Room No. 101, Ground floor)

Abstract
Contour trees are extensively used in scalar field analysis. The contour tree is a data structure that tracks the evolution of level set topology in a scalar field. Scalar fields are typically available as samples at vertices of a mesh and are linearly interpolated within each cell of the mesh. A more suitable way of representing scalar fields, especially when a smoother function needs to be modeled, is via higher order interpolants. We propose an algorithm to compute the contour tree for such functions. The algorithm computes a local structure by connecting critical points using a numerically stable monotone path tracing procedure. Such structures are computed for each cell and are stitched together to obtain the contour tree of the function. The algorithm is scalable to higher degree interpolants whereas previous methods were restricted to quadratic or linear interpolants. The algorithm is intrinsically parallelizable and has potential applications to isosurface extraction.

Speaker Bio:
Girijanandan Nucha is a master's student at IISc. He is currently working in Huawei technologies. His interests are in Scientific visualization, databases and visual data analytics.

Video Archive Go Top

 

Series: Department Seminar
Title: Towards a More Secure Aadhaar

  • Speaker: Prof. K Gopinath & Mr. Ajinkya Rajput
                   Dept. of CSA
  • Date and Time: Thursday, February 01, 2018, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Aadhaar is the national identities project of the Government of India. The main benefit of Aadhaar is expected to be better decision making using modern analytics (for eg, detecting fraud) as citizens can only use such an identity to avail of services from various government as well as private service providers; this necessarily involves building a huge store with necessary information on citizens such as mapping of ids to biometrics. Such stores raise many security and privacy concerns and therefore should be designed and analyzed very carefully. The threat model for such systems should address both internal and external attackers. Previous writings in the press and research work in this area have discussed many issues such as unwanted profiling and tracking of individuals, authentication without consent, collusion between multiple service providers leading to correlation of user data that may result in loss of privacy, suitability of biometrics chosen and the use of fake biometrics. While some analyses have suggested use of certain types of cryptographic operations to provide a solution, a comprehensive and workable solution for, say, avoiding profiling, has been lacking till recently, and there are also many problems from a larger systems perspective that need to be addressed such as access control models to constrain the access to sensitive data during collection and update of data as well as integrity of its metadata.

While “bullet proof” security is not possible for such a large system in principle, it is also not the case that certain aspects such as profiling cannot be handled through technical solutions; currently only legal provisions are available post facto for handling breaches. In this talk, we discuss solutions to a few problems, focussing especially on how to avoid profiling based on our work. The talk is expected to be accessible to a general audience but technical details will be discussed in as "simple a way as possible but not simpler”.

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: An Exploratory Framework for Cyclone Identification and Tracking

  • Speaker: Mr. Akash Anil Valsangkar
                   MSc (Engg)Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Vijay Natarajan
  • Date and Time: Monday, January 29, 2018, 11:00 AM
  • Venue: CSA Faculty Room, (Room No. 101, Ground floor)

Abstract
Analyzing depressions plays an important role in meteorology, especially in the study of cyclones. In particular, the study of the temporal evolution of cyclones requires a robust depression tracking framework. To cope with this demand we propose a pipeline for the exploration of cyclones and their temporal evolution. This entails a generic framework for their identification and tracking. The fact that depressions and cyclones are not well-defined objects and their shape and size characteristics change over time makes this task especially challenging. Our method combines the robustness of topological approaches and the detailed tracking information from optical flow analysis. At first cyclones are identified within each time step based on well-established topological concepts. Then candidate tracks are computed from an optical flow field. These tracks are clustered within a moving time window to distill dominant coherent cyclone movements, which are then forwarded to a final tracking step. In contrast to previous methods our method requires only a few intuitive parameters. An integration into an exploratory framework helps in the study of cyclone movement by identifying smooth, representative tracks. Multiple case studies demonstrate the effectiveness of the method in tracking cyclones, both in the northern and southern hemisphere.

Speaker Bio:
Akash Anil Valsangkar is a Masters student in CSA with 2.5 years of industrial experience. His interests are Data Analysis and Visualization, Machine learning and AR-VR technologies.

Video Archive Go Top

 

Series: Department Seminar
Title: From the Mundane to the Spectacular: The Meltdown and Spectre attacks

  • Speaker: Prof. Vinod Ganapathy, CSA, IISc.
  • Date and Time: Thursday, January 25, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Early this month, the popular media was rife with news articles describing Meltdown and Spectre, two devastating attacks that affected millions of computers worldwide.

This talk will provide a technical overview of these attacks. The talk will show how two age-old performance-enhancing tricks---out-of-order execution and speculative execution---by now considered mundane in the computer architecture community were put to spectacular use by the designers of the attacks.

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

Series: Department Seminar
Title: The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues

  • Speaker: Mr. Shashwat Garg
                   Eindhoven University of Technology in Netherlands
  • Date and Time: Monday, January 22, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
An important result in discrepancy due to Banaszczyk states that for any set of $n$ vectors in $mathbb{R}^m$ of $ell_2$ norm at most $1$ and any convex body $K$ in $mathbb{R}^m$ of Gaussian measure at least half, there exists a $pm 1$ combination of these vectors which lies in $5K$. This result implies the best known bounds for several problems in discrepancy. Banaszczyk's proof of this result is non-constructive and a major open problem has been to give an efficient algorithm to find such a $pm 1$ combination of the vectors. I will be talking about a recent result where we resolve this question and give an efficient randomized algorithm to find a $pm 1$ combination of the vectors which lies in $cK$ for $c>0$ an absolute constant.

This is joint work with Nikhil Bansal, Daniel Dadush and Shachar Lovett.

Speaker Bio:
Shashwat Garg is a third year PhD student at Eindhoven University of Technology in Netherlands, where he is advised by Prof. Nikhil Bansal. Previously, he completed his undergraduate studies from IIT Delhi under the supervision of Prof. Naveen Garg. His research interests are in approximation algorithms, discrepancy theory and hierarchies.

Host Faculty: Dr. Siddharth Barman

Video Archive Go Top

 

Series: Department Seminar
Title: Almost-polynomial ratio ETH-hardness of approximating Densest k-Subgraph

  • Speaker: Pasin Manurangsi
                   Theoretical Computer Science Group
                   University of California
                   Berkeley
  • Date and Time: Friday, January 19, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In the Densest k-Subgraph problem, given an undirected graph G and an integer k, the goal is to find a subgraph of G on k vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves O(n^1/4) approximation ratio (Bhaskara et al. 2010), the problem has resisted previous attempts at proving hardness of approximation with a matching ratio; in fact, the best approximation ratio ruled out under any worst case assumption is only any constant (Raghavendra and Steurer 2010). In this talk, I will outline a simple sub-exponential time reduction and a proof which provides an almost polynomial (n^{1/polyloglog n}) ratio inapproximability of Densest k-Subgraph under the exponential time hypothesis.

Host Faculty: Dr. Arnab Bhattacharyya

Video Archive Go Top

 

Series: Department Seminar
Title: Inspiring Trust in Outsourced Computations: From Secure Chip Fabrication to Verifiable Deep Learning in the Cloud

  • Speaker: Dr. Siddharth Garg
                   NYU
                   Tandon School of Engineering
  • Date and Time: Thursday, January 18, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Computations are often outsourced by computationally weak clients to computationally powerful external entities. Cloud computing is an obvious example of outsourced computation; outsourced chip manufacturing to off-shore foundries or ``fabs" is another (perhaps less obvious) example. Indeed, many major semiconductor design companies have now adopted the so-called ``fabless" model. However, outsourcing raises a fundamental question of trust: how can the client ascertain that the outsourced computations were correctly performed? Using fabless chip manufacturing and ``machine-learning as a service (MLaaS)" as exemplars, this talk will highlight the security vulnerabilities introduced by outsourcing computations and describe solutions to mitigate these vulnerabilities.

First, we describe the design of "verifiable ASICs" to address the problem of secure chip fabrication at off-shore foundries. Building on a rich body of work on the ``delegation of computation" problem, we enable untrusted chips to provide run-time proofs of the correctness of computations they perform. These proofs are checked by a slower verifier chip fabricated at a trusted foundry. The proposed approach is the first to defend against arbitrary Trojan misbehaviors (Trojans refer to malicious modifications of a chip's blueprint by the foundry) while providing formal and comprehensive soundness guarantees.

Next, we examine the "MLaaS" setting, in which both the training and/or inference of machine learning models is outsourced to the cloud. We show that outsourced training introduces new security risks: an adversary can create a maliciously trained neural network (a backdoored neural network, or a BadNet) that has state-of-the-art performance on the user’s training and validation samples, but behaves badly on specific attacker-chosen inputs. We conclude by showing how the same techniques we used design ``verifiable ASICs" can be used to verify the results of neural networks executed on the cloud.

Speaker Bio:
Siddharth Garg received his Ph.D. degree in Electrical and Computer Engineering from Carnegie Mellon University in 2009, and a B.Tech. degree in Electrical Enginerring from the Indian Institute of Technology Madras. He joined NYU in Fall 2014 as an Assistant Professor, and prior to that, was an Assistant Professor at the University of Waterloo from 2010-2014. His general research interests are in computer engineering, and more particularly in secure, reliable and energy-efficient computing. In 2016, Siddharth was listed in Popular Science Magazine's annual list of "Brilliant 10" researchers. Siddharth has received the NSF CAREER Award (2015), and paper awards at the IEEE Symposium on Security and Privacy (S&P) 2016, USENIX Security Symposium 2013, at the Semiconductor Research Consortium TECHCON in 2010, and the International Symposium on Quality in Electronic Design (ISQED) in 2009. Siddharth also received the Angel G. Jordan Award from ECE department of Carnegie Mellon University for outstanding thesis contributions and service to the community. He serves on the technical program committee of several top conferences in the area of computer engineering and computer hardware, and has served as a reviewer for several IEEE and ACM journals.

Host Faculty: Prof. Vinod Ganapathy & Prof. Aditya Gopalan (ECE)

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: A Fine-Grained Dynamic Information Flow Analysis for Android Apps

  • Speaker: Mr. Shyam Sankaran
                   M.Sc. (Engg) student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Aditya S Kanade
  • Date and Time: Monday, January 15, 2018, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Android has been steadily gaining popularity ever since its launch in 2008. One of the major factors for this is the easy availability of a large variety of apps. They range from simple apps such as calculator apps to apps which can help people maintain their schedules and thus manage many aspects of their lives. In addition, a lot of free apps are available to the user thanks to the power of in-app purchases and advertisements. However, these also raise many security concerns. Apps are privy to a lot of private information regarding the user, such as his contacts, location, etc. It is essential to ascertain that apps do not leak such information to untrustworthy entities. In order to solve this problem, there have been many static and dynamic analyses which aim to track private data accessed or generated by the app to its destination. Such analyses are commonly known as Information Flow analyses. Dynamic analysis techniques, such as TaintDroid, tracks private information and alerts the user when it is accessed by specific API calls. However, they do not track the path taken by the information, which can be useful in debugging and validation scenarios.

The first key contribution of this thesis is a model to perform dynamic information flow analysis, inspired by FlowDroid and TaintDroid, which can retain path information of sensitive data in an efficient manner. The model instruments the app and uses path-edges to track the information flows during a dynamic run. We describe the data structure and transfer functions used, and the reasons for its design based on the challenges posed by the Android programming model and efficiency requirements. The second key contribution is the capability to trace the path taken by the sensitive information based on the information obtained during the analysis, as well as the capability to complement static analyses such as FlowDroid with the output of this analysis. The tests conducted on the implemented model using DroidBench and GeekBench 3 show the precision and soundness of the analysis, and a performance overhead of 25% while real-world apps show negligible lag. All leaks seen in DroidBench where successfully tracked and were verified to be true positives. We tested the model on 10 real-world apps where we find on average about 16.4% of the total path-edges found by FlowDroid.

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Fully Resilient Non-Interactive ID-Based Hierarchical Key Agreement.

  • Speaker: Mr. Mayank Tiwari
  • Faculty Advisor: Prof. Sanjit Chatterjee
  • Date and Time: Thursday, January 11, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Fully Resilient Non-Interactive Id-based Hierarchical Key Agreement Non-Interactive Key Agreement (NIKA) is a cryptographic primitive which allows two parties to agree on a shared key without any interaction. Identity-based Non-Interactive Key Agreement (ID-NIKA) allows each party to compute shared secret key using its own secret key and the peer’s identity. ID-NIKA can be used to establish shared secret keys in Ad-hoc networks using minimal battery power and communication.

Mobile Ad-hoc NETwork (MANET) is a network of mobile and moderately resource constrained devices communicating through a wireless medium. Examples of standard MANET devices are laptops, cellphones etc. Due to the inherent characteristics like mobility, dynamic topology and lack of centralized infrastructure, MANETs face some serious security issues. We are particularly interested about ID-NIKA in MANETs. This is of crucial interest for secure communication between two nodes in MANETs.

In 2008, Gennaro et al. introduced a scheme called Hybrid Hierarchical Key Agreement Scheme (HH-KAS). HH-KAS uses a linear hierarchical key agreement scheme at the non-leaf levels and a key agreement scheme due to Sakai et al. (referred as SOK-KAS) at the leaf level. HH-KAS is (i) non-interactive, (ii) identity based, (iii) hierarchical and is (iv) fully resilient against node compromises at leaf level and resilient against node compromises upto certain threshold values in non-leaf levels. Thus one can say that HH-KAS is partially resilient against node compromises. In their paper the authors claim that there is no key agreement scheme for MANETs in the literature, with all above four properties. This was motivated as an interesting open problem in this area.

Guo et al. proposed a scheme known as Strong Key Agreement Scheme (SKAS) in 2011. The authors claimed it a potential solution to the open problem posed by Gennaro et al. in their work. However, in 2014, Zhu et al. showed a concrete attack on SKAS. This attack makes SKAS practically useless for real life applications.

Our main contribution is a hybrid scheme using two already existing schemes. Our scheme uses a deterministic key pre-distribution scheme by Lee and Stinson termed as Basic Id One-way function Scheme (BIOS) at level 1 (where root is at level 0). Beyond level 1, we use SOK-KAS for key agreement. We refer our scheme as BIOS-SOK key agreement. BIOS and SOK schemes satisfy properties (i), (ii) and (iv) but none of them is hierarchical in nature. In our work we have made an amalgam of both schemes which is hierarchical in nature. Thus, BIOS-SOK scheme satisfies (i), (ii), (iii) and is also fully resilient against arbitrary number of node compromises at any level.

BIOS-SOK scheme also possesses the benefits of low space requirement, low shared key computation time and better scalability for many real-life applications when compared with the scheme of Gennaro et al. In HH-KAS, the key agreement is carried out only at the leaf level. In BIOS-SOK scheme, any two nodes in the hierarchy (at same or different levels) can compute shared secret key. We also provide a rigorous security analysis for our scheme in a stronger security model compared to the security model used for HH-KAS.

Video Archive Go Top

 

Series: Department Seminar
Title: Two Modeling Primitives for Computer Aided Geometric Design

  • Speaker: Dr Jinesh Machchhar
                   Post doctoral Fellow, Technion
  • Date and Time: Wednesday, January 10, 2018, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Computer Aided Geometric Design concerns development of algorithms and accompanying software, towards design of parts and structures with a high degree of numerical precision. Target application domains include design of automobiles, aircrafts and buildings, among others. In this talk we discuss two kernel level modeling primitives. First, we propose a comprehensive algorithmic framework for computation of solid sweeps. This involves computing the boundary of the swept volume generated by moving the input solid along the input one-parameter-family of rigid motions in three dimensional space. In particular, we discuss local issues such as the parametrization of the boundary surface, detection and elimination of self-intersections, as well as global issues such as body-check and the topological data associated with the swept volume. Several examples from a prototype implementation in the ACIS modeling kernel will be shown. Applications include CNC machining verification, product handling and collision detection. Second, we demonstrate a robust computational interface for precise modeling of microstructures towards 3D printing. This is achieved through functional composition of B-spline functions and allows separate design of the micro and the macro structures of an object. In particular, we demonstrate construction of recursive, fractal-like microstructures which are composed of trivariate tiles with C0-discontinuities. Applications include design of porous and composite materials. This is joint work with Milind Sohoni, Bharat Adsul and Gershon Elber.

Speaker Bio:
Jinesh Machchhar is a post-doctoral fellow in the faculty of computer science at Technion-Israel Institute of Technology. He obtained his Ph.D. from IIT Bombay under the guidance of Prof. Milind Sohoni and Prof. Bharat Adsul in 2015. He did his M.Tech from IIT Bombay and his bachelor of engineering from South Gujarat University. His research interests include geometric modeling, surface design and analysis, and software development for computer aided design and manufacturing.

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

Copyright: CSA, IISc 2017      Phone: +91-80-22932368          Fax: +91-80-23602911 Travel Blog    Feedback    Credits