Title: Dynamic Analysis of Data-Structure Traversals for Identifying Performance Bugs

Description: Speaker: Mr. Rohan Padhye

Time: Friday, 19 January 2018, 11:30am
Venue: Conference Room, 01st Floor, C Block, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building

A fundamental operation on a data structure is its traversal, in which an algorithm systematically visits some or all of its data items. Algorithms that perform repeated traversals of data structures are often the source of pesky performance problems that are only triggered with special pathological inputs. Unfortunately, extensive performance benchmark suites are not as commonly available as simple unit tests that exercise benign behavior, making such bugs hard to find.

This talk will describe Travioli, a dynamic program analysis technique to identify and visualize complex traversals of arbitrary, dynamically-typed data-structures built from arrays and/or reference links, and that use either loops or recursion. Travioli can identify potential performance bugs involving redundant traversals by analyzing the execution of only simple unit tests. Travioli has already identified two previously unknown performance bugs in widely used JavaScript frameworks D3.js and Express.js, and is the basis for our subsequent work on automatic worst-case input generation.

Speaker's Profile:
Rohan Padhye is a third-year PhD student at the University of California, Berkeley, where he is advised by Prof. Koushik Sen. Rohan graduated with an M.Tech in CSE from IIT Bombay in 2013, where he worked with Prof. Uday Khedker on static heap alias analysis and developed VASCO, a framework for inter-procedural data-flow analysis using value contexts. Subsequently, Rohan worked at IBM Research India for two years developing productivity tools using data mined from code versioning repositories such as Git. At UC Berkeley, Rohan is investigating dynamic program analysis techniques to automatically generate test inputs that expose bugs and security vulnerabilities.

University of California, Berkeley

Prof. Uday Khedker

Date: Friday, 19 January, 2018
Time: 11:30am IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Sunday, 20 January, 2019 6:04am IST
Send Reminder: Yes  -  406 hours 49 minutes before start
Participants: Department Calendar
<seminar@iitb.ac.in> (External User)
<all@cse.iitb.ac.in> (External User)
_NUC_department <office@cse.iitb.ac.in> (External User)