Transcript Lori_Pollock

Developing Natural Language-based
Software Analyses and Tools
to Expedite Software Maintenance
Lori Pollock
Collaborators: K. Vijay-Shanker, Emily Hill,
GiriprasadSridhara
Problem
Modern software is large and complex
Softwaremaintenance:
- search/locate
- navigate
- understand
- modify
object oriented class hierarchy -> Automated Support
Successesin Software Maintenance Tools
 Good with local
tasks
 Good with
traditional structure
object oriented class hierarchy
Challengesin Software Maintenance Tools
 Scattered tasks
are difficult
 Programmers
use more than
traditional
program
structure
object oriented class hierarchy
Observations
public interface Storable{...
KeyinInsight:
//Store the fields
a file....
undo action
Programmers leave natural language clues that
update drawing
voidsoftwaremaintenance
Circle.save()
canpublic
benefit
tools
activate tool
save drawing
object oriented system
Studies on choosing identifiers
I don’t care
about names.
So, I could use
x, y, z. But, no one
will understand
my code.
Carla, the compiler writer
Pete, the programmer
 Impact of human cognition on names [Liblit et al. PPIG 06]
 Metaphors, morphology, scope, part of speech hints
 Hints for understanding code
 Analysis of Function identifiers
[Caprile and Tonella WCRE 99]
 Lexical, syntactic, semantic analysis
 Use for software tools: metrics, traceability, program understanding
Our Research Focus and Impact
Search
Exploration
Understanding
…
Software Maintenance Tools
NLPA
Natural Language Analysis
Abbreviations
Word relations
(synonyms,
antonyms, …
Part of speech
tagging
…
Our Research Contributions…
Motivated use
of NL clues
during maintenance
[MACS 05, LATE 05]
FindConcept
Concern location tool
[ASE 05]
Clue Extraction +
NL-based Program
Representation
[AOSD 06, IET 08]
iTimna
Aspect Miner
Dora the
Program Explorer
[AOSD 07, PASTE 07]
Abbreviation
Expander
[MSR 08]
Word Relation Tool
Comparison Study
[ICPC 08]
[ASE 07]
Automatic Natural Language Clue
Extraction from Source Code
What was Pete thinking
when he wrote this code?
Key Challenges:
 Decode name usage
 Develop automatic NL clue
extraction process (focused on
Java)
 Create NL-based program
representation
Molly, the Maintainer
Natural Language: Which Clues to Use?
Software Maintenance
 Typically focused on actions
 Objects are well-modularized
Focus on actions
 Correspond to verbs
 Verbs need Direct Object
(DO)
Extract verb-DO
pairs
Extracting Verb-DO Pairs
Two types of extraction
Extraction
from
method
signatures
Extraction
from
comments
class Player{
/**
* Play a specified file with specified time interval
*/
public static boolean play(final File file,final float fPosition,fina
fCurrent = file;
try {
playerImpl = null;
//make sure to stop non-fading players
stop(false);
//Choose the player
Class cPlayer = file.getTrack().getType().getPlayerImpl(
…
Extracting Clues from Signatures
1. Part-of-speech tag method name
2. Chunk method name
3. Identify Verb and Direct-Object (DO)
public UserList getUserListFromFile( String path ) throws IOException {
try {
POS Tag
get<verb> User<adj> List<noun>From <prep>File <noun>
File tmpFile = new File( path );
return parseFile(tmpFile);
Chunk
get<verb phrase> User List<noun phrase>FromFile <prep phrase>
} catch( java.io.IOException e ) {
thrownew IOrException( ”UserList format issue" + path + " file " + e );
Representing Verb-DO Pairs
Action-Oriented Identifier Graph (AOIG)
verb1
verb2
verb1, DO1
verb3
verb1, DO2
use
use
DO1
verb3, DO2
use
use
use
DO2
use
use
DO3
verb2, DO3
use
source code files
Action-Oriented Identifier Graph (AOIG)
Example
play
add
play, file
remove
play, playlist
use
use
file
remove, playlist
use
use
use
playlist
use
use
listener
add, listener
use
source code files
Evaluation of Clue Extraction
 Compared automatic vs ideal (human) extraction
 300 methods from 6 medium open source programs
 Annotated by 3 Java developers
 Promising Results
 Precision: 57%
 Recall: 64%
 Context of Results
 Did not analyze trivial methods
 On average, at least verb OR direct object obtained
Using AOIG in Concern Location
Find, collect, and understand all source
code related to a particular concept
Concerns are
often crosscutting
State of the Art for Concern Location
 Mining Dynamic Information [Wilde ICSM
Reduced to
00]
similar problem
 Program Structure Navigation [Robillard
Slow
FSE 05,
FEAT, Schaefer ICSM 05]
 Search-Based Approaches
 RegExp[grep, Aspect Mining Tool 00]
 LSA-Based [Marcus 04]
 Word-Frequency Based [GES 06]
Fast
Fragile
Sensitive
No Semantics
Limitations of Search Techniques
1.
2.
3.
Return large
result sets
Return irrelevant
results
Return hard-tointerpret result
sets
Find-Concept Search Tool
1. More
effective search
2. Improved
search terms
Source Code
3. Understandable
results
concept
Method a
query
Find-Concept
NL-based
Code Rep
Recommendations
Method c
Method d
Natural
Language
Information
Method b
Method e
Result Graph
Underlying Program Analysis
 Word Recommendation Algorithm
 Stemmed/Rooted: complete, completing
 Synonyms: finish, complete
 Co-location: completeWord()
 Uses traversals of Action-oriented
identifier graph (AOIG)
Experimental Evaluation
Find Concept, GES, ELex
 Research Questions
 Which search tool is most effective at forming and
executing a query for concern location?
 Which search tool requires the least human effort to
form an effective query?
 Methodology:
18 developers completenine concern locationtaskson
medium-sized (>20KLOC) programs
 Measures:
Precision (quality), Recall (completeness),
F-Measure (combination of both P & R)
Overall Results
Across all tasks
 Effectiveness
 FC > Elex with statistical
significance
 FC >= GES on 7/9 tasks
 FC is more consistent than GES
 Effort
 FC = Elex = GES
FC is more consistent and more effective in
experimental study without requiring more effort
Our Research Focus and Impact
Search
Exploration
Understanding
…
Software Maintenance Tools
NLPA
Natural Language Analysis
Abbreviations
Word relations
(synonyms,
antonyms, …
Part of speech
tagging
…
Dora the Program Explorer*
Query
Natural Language Query
• Maintenance request
• Expert knowledge
• Query expansion
Program Structure
• Representation
• Current: call graph
• Seed starting point
Dora
Relevant Neighborhood
• Subgraph relevant to query
* Dora
Relevant
Neighborhood
comes from exploradora, the Spanish word for a female explorer.
State of the Art in Exploration
 Structural (dependence, inheritance)
 Slicing
 Suade [Robillard 2005]
 Lexical (identifier names, comments)
 Regular expressions: grep, Eclipse search
 Information Retrieval: FindConcept [Shepherd
2007],
Google Eclipse Search [Poshyvanyk 2006]
Dora: Using Program Structure + Ids
Key Insight: Automated tools can use program
structure and identifier names to save the
developer time and effort
Example Scenario:
 Program: JBidWatcher, an eBay auction sniping program
 Bug: User-triggered add auction event has no effect
 Task: Locate code related to ‘add auction’ trigger
 Seed: DoAction() method, from prior knowledge
Using only structural information
Looking for:
‘add auction’ trigger
 DoAction() has 38 callees,
only 2/38 are relevant
DoAction()
Relevant
Methods
 Locates locally relevant items,
but many irrelevant
DoAdd()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
And what if you wanted to explore
more than one edge away?
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoPasteFromClipboard()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
Irrelevant Methods
DoNada()
DoNada()
DoNada()
Using only lexical information
 50/1812 methods contain
matches to ‘add*auction’
regular expression query
 Only 2/50 are relevant
 Locates globally relevant
items, but many irrelevant
Combining Structural &
Lexical Information
Looking for:
‘add auction’ trigger
DoAction()
 Structural: guides exploration
from seed
Lexical: prunes irrelevant edges
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoAdd()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
DoNada()
Relevant
Neighborhood
DoNada()
DoNada()
DoPasteFromClipboard()
DoNada()
The Dora Approach
Prune irrelevant structural edges from seed
Determine method relevance to query
 Calculate lexical-based relevance score
Prune low-scored methods from
neighborhood
Recursively explore
Evaluation of the Dora Approach
 Evaluated on 9 concerns
 Lexical + structural >
structural
 However, success highly
dependent on lexical
scoring performance
Structure
only
31
Our Research Focus and Impact
Search
Exploration
Understanding
…
Software Maintenance Tools
NLPA
Natural Language Analysis
Abbreviations
Word relations
(synonyms,
antonyms, …
Part of speech
tagging
…
Automatic Abbreviation Expansion
• Don’t want to miss relevant code with abbreviations
• Given a code segment, identify character sequences
that are short forms and determine long form
1.Split Identifiers:
non-dictionary word
no boundary
 Punctuation
 Camel case
 No boundary
 e.g., strlen
2.Identify non-dictionary
words
3.Determine long form
• Approach: Mine expansions from code [MSR 08]
Simple Dictionary Approach
 Manually create a lookup table of common
abbreviations in code
- Vocabulary evolves over time, must maintain
table
- Same abbreviation can have different
Control Flow Graph
expansions depending on domain AND context:
?
cfg
Context-Free Grammar
configuration
configure
Types of Non-Dictionary Words
Single-Word
 Prefix (attr, obj, param, i)
 Dropped Letter (src, evt, msg)
Multi-Word
 Acronyms (ftp, xml, [type names])
 Combination (println, doctype)
Others
 No boundary (saveas, filesize)
 Misspelling (instanciation,
zzzcatzzzdogzzz)
Long Form Search Patterns
Given short form arg, we search for
regular expressions matching long forms
in code:
 Single-Word
Prefixargument
Dropped letteraverage
 Multi-Word
Acronym attribute random group
Combinationaccess rights
Search Pattern Order
Search by abbreviation type:
Multi-Word
Conservative
Acronym
Single Word
Prefix
How do we identify potential
long forms for each type?
Greedy
Combination
Dropped
Letter
Context-based Approach through
Scope
 Inspired by static scoping, start from method
containing abbreviation and search increasingly
broader “scopes” until clear winner:
1. JavaDoc
2. Type Names of declared variables
3. Method Name
4. Statements
5. Referenced identifiers and string literals
6. Method comments
7. Class comments
What if no long form found?
Fall back to Most Frequent Expansion
(MFE)
MFE leverages successful local
expansions and applies throughout the
program
1. Program: provides domain knowledge
2. Java: more general programming
knowledge
Experimental Evaluation
Number of Correct Expansions
250
200
 Scope 57% more accurate than
state of the art LFB
150
 Scope 30% more accurate than
Java MFE
100
 Program MFE acceptable
approximation when speed
more important than accuracy
50
0
No
Exp
LFB
Java Prog Our
MFE MFE Scope
Accuracy: 22% 40% 45% 54% 59%
63%
In Conclusion…
 Evaluation studies indicate
Natural language analysis has far more potential to
improve software maintenance tools than we
initially believed
 Existing technology falls short
Synonyms, collocations, morphology, word
frequencies, part-of-speech tagging, AOIG
 Keys to further success
Improve recall
Extract additional NL clues