Search-Based Software Engineering:Foundations and Recent Applications

Ali Ouni
Software Engineering Lab, Osaka University, Japan

5th Asian Workshop of Advanced Software Engineering (AWASE’16), 19-20 March, 2016, Nara, Japan

Engineering Words

Tolerance

With acceptable bounds

Optimise

Improve performance

Reduce cost

Optimize

Within constraints

2

Engineering Words

Tolerance

With acceptable bounds

Optimise

Improve performance

Reduce cost

Optimize

Within constraints

Optimise
Optimizeso good they named it twice!

SBSE
3

What is SBSE ?
The term “Search-Based Software Engineering” (SBSE) coined in 2001 by Mark Harman.

• SBSE uses intelligent search techniques to explore
large search spaces, guided by a fitness functionthat captures properties of the desirable solutions
we seek.
Genetic Programming
Ant Colonies

Harmony Search
Hill Climbing

Tabu SearchParticle Swarm Optimization
Simulated Annealing4What is SBSE ?

SBS
E

Search-BasedOptimization

Software Engineering

Search-based techniques
••
•
•
••
•

SoftwareEngineering

Genetic algorithm
Ant colony optimization
Simulated annealing
Particle swarm optimization
NSGA-II
NSGA-III...

SBSE•
••••
••

Search-based Testing
Search-based refactoringSearch-based software management
Search-based requirements engineering
Search-based Fault Location
Search-based program repair
...

••
•
•••
•

Automated test generation
Code refactoring
Software proj. management
Requirements engineering
Fault localization
Program repair...

5Conventional vs Search-based• Conventional Software Engineering• Write a method to construct a good solution• Search Based Software Engineering• Write a method to guide you to the best solution

6

SBSE for software refactoring• SBSE formulation
1. Identify a software engineering problem
2. Identify the desirable properties of a good solution you would like tohave
3. Formulate them in a measurable way
4. Use them as a way for searching the space of possible solutions
Optimize:
1. Coupling
2. Cohesion

Librairy_Main_Control-borrow_date_Book-current_Book-current_Catalog-fine_Amount-listOfCatalogs-librairy_opened-reserved_Book-return_date_Book

Catalog-…
+…()+add_Book()+archive_Catalog()+borrow_Book()+check_Availab_Book()+check_Delay_Book()+check_FineAmount()+check_ValidityCard()+close_Librairy()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+issue_LibrairyCard()+list_Catalogs()+open_Librairy()+print_Catalog()+remove_Book()+reserve_Book()+return_Book()+search_Book()+search_Catalog()+sort_Catalog()

Data Class

Book-…

Next ?
Catalog

Librairy_Main_Control-borrow_date_Book-current_Book-current_Catalog-librairy_opened-reserved_Book-return_date_Book+add_Book()+archive_Catalog()+borrow_Book()+check_Availab_Book()+check_Delay_Book()+check_FineAmount()+display_Book()+display_Catalog()+do_Inventory()+issue_LibrairyCard()+list_Catalogs()+open_Librairy()-current_Book

Catalog-current_Book+archive_Catalog()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+print_Catalog()
Data Class

Librairy_Main_Control-current_Catalog-listOfCatalogs+sort_Catalog()+add_Book()+list_Catalogs()+remove_Book()+search_Book()+search_Catalog()

Data Class

Book-borrow_date_Book-return_date_Book-reserved_BookBook-borrow_date_Book-return_date_Book-reserved_Book

NewClass_2-librairy_opened+…()+archive_Catalog()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+print_Catalog()+return_Book()+borrow_Book()+check_Delay_Book()+reserve_Book()+check_Availabi_Book()+close_Librairy()+open_Librairy()

NewClass_1+return_Book()+borrow_Book()+check_Delay_Book()+reserve_Book()+check_Availabi_Book()-fine_Amount+chek_FineAmount()+check_ValidityCard()+issue_LibrairyCard()

Data Class

7

SBSE in a nutshell …
Software Engineering
Problem

Software Engineering

Solution representation
encoding

Optimization
Techniques

Fitness
Function

Search Based
Software Engineering

Function defined toevaluate solutions

ChangeoperatorSearch Problem

8

Is SBSE interesting?

let’s listen to software engineers ...

... what sort of things do they say?
9

Software Engineers Say…
Requirements: We need all requirements that balance softwaredevelopment cost and customer satisfaction
Management:

We need to reduce risk while maintaining completion
time

Design:We need increased cohesion and decreased coupling

Testing:

We need fewer tests that find more nasty bugs

Refactoring:

We need to optimize for all metrics M1,..., Mn

All have been addressed in the SBSE literature!
10

… but …
why is SBSE growing very fast?
• TOP conferences in SE• ICSE and FSE : whole sessions to SBSE
• TOP conferences in Evolutionarycomputation• GECCO: have track dedicated to SBSE

• Dedicated international conferences:(SSBSE, SBST) and many other workshops

Publication growth up to 2012
• 1,600 authors• nearly 300 institutions• more than 40 countries

11Search-based refactoring• Systems, like people, get old : increase in complexity anddegrade in effectiveness• Software changes frequently• Add new requirements• Adapt to environment changes• Correct bugs

• Changing a software can be a challenging task
• These changes may degrade their design and QoS• The original developers are not around anymore• Maintain a high level of quality during the life cycle of asoftware system
12Software refactoring• The process of improving a code after it has been written bychanging its internal structure without changing the external
behavior (Fowler et al., ‘99)
• Examples: Move method, extract class, move attribute, ...
• IDEs: Eclipse, NetBeans, …

• Two steps

Detection of codefragments to improve(e.g., code-smells)

Identification ofrefactoring solutions

13Step 2: Refactoring
Catalog

Librairy_Main_Control-borrow_date_Book-current_Book-current_Catalog-fine_Amount-listOfCatalogs-librairy_opened-reserved_Book-return_date_Book+add_Book()+archive_Catalog()+borrow_Book()+check_Availab_Book()+check_Delay_Book()+check_FineAmount()+check_ValidityCard()+close_Librairy()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+issue_LibrairyCard()+list_Catalogs()+open_Librairy()+print_Catalog()+remove_Book()+reserve_Book()+return_Book()+search_Book()+search_Catalog()+sort_Catalog()-current_Book
Catalog-…
+…()

Librairy_Main_Control

Data Class-current_Catalog-listOfCatalogs

Book

Refactoring-…
+…()

Data Class

Move method
Extract classMove field
Inline class…

+archive_Catalog()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+print_Catalog()+sort_Catalog()+add_Book()+list_Catalogs()+remove_Book()+search_Book()+search_Catalog()

NewClass_2-librairy_opened+close_Librairy()+open_Librairy()

NewClass_1-fine_Amount

Data ClassBook-borrow_date_Book-return_date_Book-reserved_Book+return_Book()+borrow_Book()+check_Delay_Book()+reserve_Book()+check_Availabi_Book()

Data Class+chek_FineAmount()+check_ValidityCard()+issue_LibrairyCard()

Blob14

Search-based Refactoring
Code-smells
detection rules

Code to be
refactored

List ofpossible
refactorings

Search-based Refactoring(NSGA-II)

Suggestedrefatorings

Semantic
information
Ali Ouni, Marouane Kessentini, Houari Sahraoui, Katsuro Inoue, Kalyanmoy Deb, “Multi-criteria Code Refactoring
Suggestions: An Industrial Case Study”, ACM Transactions on Software Engineering and Methodology (TOSEM), 2016.
15

NSGA-II adaptation
 Solution representation

 Individual = Sequence of refactoring operations
1

moveMethod

2

pullUpAttribute3

extractClass

4

inlineClass

5

extractSuperClass

6

inlineMethod

 Controlling parameters
Refactorings

Controlling parameters

move method
move field
pull up field
pull up methodpush down field
push down method
inline classextract class(sourceClass, targetClass, method)(sourceClass, targetClass, field)(sourceClass, targetClass, field)(sourceClass, targetClass, method)(sourceClass, targetClass, field)(sourceClass, targetClass, method)(sourceClass, targetClass)(sourceClass, newClass)

16

NSGA-II adaptation

 Four refactoring objectives
1.

Quality

2.

Code changes
3.

Minimize the number of code-smells

Minimize the number of code changes required when applying refactoring

Preserve semantic coherenceMaximize semantics coherence of the refactored code17

Refactoring objectives


Number of code changes
Librairy_Main_Control-borrow_date_Book-current_Book-current_Catalog-fine_Amount-listOfCatalogs-librairy_opened-reserved_Book-return_date_Book+add_Book()+archive_Catalog()+borrow_Book()+check_Availab_Book()+check_Delay_Book()+check_FineAmount()+check_ValidityCard()+close_Librairy()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+issue_LibrairyCard()+list_Catalogs()+open_Librairy()+print_Catalog()+remove_Book()+reserve_Book()+return_Book()+search_Book()+search_Catalog()+sort_Catalog()

Catalog-…

Solution 1
1. Move method
2. Extract class
3. Move field
4. Move method
5. Move method+…()

Catalog-current_Book

1.
2.
3.
4.
5.

Solution 2
Move method.
Move method
Inline classMove field
Extract class

Data ClassBook

Refactoring

Librairy_Main_Control+archive_Catalog()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+print_Catalog()-current_Catalog-listOfCatalogs

Data Class+sort_Catalog()+add_Book()+list_Catalogs()+remove_Book()+search_Book()+search_Catalog()Book-borrow_date_Book-return_date_Book-reserved_Book

-…
+…()

Data Class

Code-smell: Blob

Solution 3
1. Move method
2. Extract class
3. Move field
4. Move method
5. Move method
6. Inline class
7. Move field
8. Extract class
9. Move method
10 Move field

NewClass_2-librairy_opened+close_Librairy()+open_Librairy()

1.
2.
3.
4.
5.
6.
7.

Solution 4
Move method.
Move method
Inline classMove field
Extract classMove field
Extract class

NewClass_1-fine_Amount+return_Book()+borrow_Book()+check_Delay_Book()+reserve_Book()+check_Availabi_Book()

Data Class+chek_FineAmount()+check_ValidityCard()+issue_LibrairyCard()

18

Refactoring objectives


Semantic coherence
Librairy_Main_Control

NewClass_2-librairy_opened+close_Librairy()+open_Librairy()NewClass_1-fine_Amount+chek_FineAmount()+check_ValidityCard()+issue_LibrairyCard()

NewClass_1-fine_Amount+chek_FineAmount()+check_ValidityCard()+issue_LibrairyCard()-borrow_date_Book-current_Book-current_Catalog-fine_Amount-listOfCatalogs-librairy_opened-reserved_Book-return_date_Book+add_Book()+archive_Catalog()+borrow_Book()+check_Availabi_Book()+check_Delay_Book()+check_FineAmount()+check_ValidityCard()+close_Librairy()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+issue_LibrairyCard()+list_Catalogs()+open_Librairy()+print_Catalog()+remove__Book()+reserve_Book()+return_Book()+search_Book()+search_Catalog()+sort_Catalog()

Code-smell: Blob

Catalog-current_Book+archive_Catalog()+create_cheap_Book()+display_Book()+display_Catalog()+do_Inventory()+print_Catalog()Book-borrow_date_Book-return_date_Book-reserved_Book+return_Book()+borrow_Book()+check_Delay_Book()+reserve_Book()+check_Availabi_Book()

19

Evaluation
Studied systems

Systems

Release# classes

GanttProject
Rhino
JFreeChartJHotDraw
Xerces-J
Apache Ant

v1.10.2
v1.7R1v1.0.9v6.1v2.7.0
v1.8.2

245
305
521
585
991
1191

# codesmells
4969722591112

KLOC
4142
170
21240
255

Three code-smell types
 Blob
 Spaghetti code Functional decomposition

20

Empirical evaluation
Quantitative
Number of fixed code smells
 Number of code changes
 QMOOD: Effectiveness, Flexibility, Reusability, Understandability
Qualitative Survey: evaluate the “relevance” of the suggested refactorings Sample of 10 refactoring operations

 18 subjects
Comparison to state-of-the-art research Harman et al 2007, Basic GA approach21

Refactoring results
Systems
XercesJFreeChart

GanttProject

AntApache

JHotDraw

Rhino
Average(all systems)

Approach

Smellscorrection

Semantic
coherence

Changes
score

NSGA-II
Harman et al. '07
GA-based approach
NSGA-II
Harman et al. '07
GA-based approach
NSGA-II
Harman et al. '07
GA-based approach
NSGA-II
Harman et al. '07
GA-based approach
NSGA-II
Harman et al. '07
GA-based approach
NSGA-II
Harman et al. '07
GA-based approach
NSGA-II
Harman et al. '07
GA-based approach

83% (55|66)
N.A
89% (59/66)
86% (49|57)
N.A
91% (52\57)85% (35|41)
N.A
95% (39|41)
78% (64|82)
N.A
80% (66|82)
86% (18|21)
N.A% (|21)
85% (52|61)
N.A
87% (53|61)
84%
N.A
89%

81 %

3843

41 %

2669

37 %

4998

82 %

2016

36 %
37 %

3269
3389

80 %

2826

23 %
27 %

4790
4697

78 %

4690

40 %
30 %

6987
6797

80 %

2231

37 %
43 %

3654
3875

80 %

1914

37 %
32 %
80 %
36 %
34 %

2698
3365
2937
4011
4520

22Refactoring results23

SBSE Validation

24

Refactoring distribution

25

Conclusion• SBSE: write a fitness function to guide automated search• SBSE formulation
1. Identify the desirable properties of a good solution you would like to have
2. Formulate them in a measurable way
3. Use them as a way for searching the space of possible solutions• SBSE is applied to solve problems in all software lifecycle• Requirements engineering• Software project management• Design• Refactoring• Software testing• Provides scalable, realistic, robust and generic solutions
26

Thank You!
Questions?