Introduction

Society's reliance and dependence on computers is nowhere more obvious than in the ubiquity of hand-held devices. The typical teenager will go no more than a few minutes per day without touching either a cell phone, MP-3 player, a hand-held gaming console, or all three (perhaps in the form of just one device). From texting to listening to music, this part of society is literally ``attached'' to at least one hand-held device most every waking minute of the day. In parallel, we are observing the growing diffusion of ``smart'' devices, e.g., routers, set-top boxes, GPS navigators, which operate under minimal operating systems with very limited storage and memory size.

This reliance on hand-held devices has been quantified recently: Sales of hand-held devices to end users totaled 1.211 billion units in 2009 and the first quarter of 2010 showed a 17% increase from the same period in 2009 [1]. eMarketer [2] forecasts that worldwide users will reach 4.3 billion in 2012. In 2008, Google introduced a new operating system and software development kit, Android, for such hand-held devices [3]. In May 2010, Eric Schmidt, Google's chairman and CEO, revealed that company's partners are shipping about 65,000 Android hand-sets per day [4]. If the rate were to be extended over 2011, there would be 24 million new Android-based hand-sets shipped. On April 21, 2009, Apple reported that over a billion iPhone applications were downloaded in just over a year. Other vendors, such as HTC and Motorola, expect conservatively to sell 20 million units per year in 2010.

[1] Gartner. Gartner says worldwide mobile phone sales grew 17 per cent in first quarter 2010. [Online; accessed 08-June-2010].
[2] eMarketer. How big will mobile get? [Online; accessed 08-June-2010].
[3] T. L. Cheung, K. Okamoto, F. Maker, III, X. Liu, and V. Akella. Markov decision process (MDP) framework for optimizing software on mobile phones. In EMSOFT'09: Proceedings of the seventh international conference on Embedded software}, pages 11-20, 2009. ACM Press.
[4] G. Byrne. Google's momentum is growing in the mobile handset market. [Online; accessed 08-June-2010].

Questions

Questions that a manager working for MobileMail, a software company specialised in porting software programs into handheld devices include:

• How are my developers of desktop applications making the foray into handheld devices?
• What tools or techniques are available to assist my developers in deciding what features to port to a handheld as they miniaturize my product?
• What if users of the application have differing opinions on what features should be ported?
• How can my developers deal with the constraints that are inherent with handheld devices, such as size of the screen, memory, and so on?
• How can my developers decide on the optimal set of features to port to a handheld device while not violating the constraints of the device?

Our Answer

We present MoMS, a novel process for the multi-objective miniaturization of software. MoMS directs (1) the elicitation of a set of pre-requirements (PRs) from multiple customers, including program concepts and environment, customer expectations, etc., (2) the consolidation of these PRs, (3) the identification of the implementation units corresponding to each PR (if any) to obtain features, (4) the identification of the device properties required by features and device constraints, (5) the selection of the features to port through a multi-objective optimization and generation of the miniaturized program.

The problem of selecting the (near) optimal set of features with the objective of satisfying customers and some resource constraints is a constrained multi-objective optimization problem. Different customers may require different features: a company might not satisfy one customer by providing her the set of required features (while meeting constraints imposed by the device) without dis-satisfying other customers. Also, satisfying some customers' PRs may cause an increase of device resource usage by the program. A project manager could painstakingly try to identify the "best" set of features satisfying most of her customers but, without an automated approach, she would never know if she has truly chosen the best set of features.

More in our technical report (number EPM-RT-2010-04) and in the page dedicated to the accompanying data

Other Related Works

Di Penta et al. [1] [2] presented a case study focused on the refactoring of a geographical information system (GRASS) operating on hand-held devices. Their effort was aimed at reducing code duplications, eliminating unused files, restructuring system libraries, and reorganizing into shared libraries. This approach does not identify links between user requirements and miniaturized code to satisfy the maximum number of stakeholders with less source code.

Bodhuin et al. [3] proposed a search-based approach for dynamically re-packing downloadable programs. The approach exploits dynamic data to re-package Java classes into Jars. It collects dynamic data by executing the instrumented programs. First, it re-package classes is to determine groups of classes used by the same set of scenarios. Second, it uses genetic algorithms to further improve optimization problem. It group together some of the class cluster obtained in the first step. For instance, in case some groups are too small, further grouping could reduce the jar overhead. They evaluated their approach on one medium-sized program.

[1] M. Di Penta, M. Neteler, G. Antoniol, and E. Merlo. Knowledge-based library re-factoring for an open source project. In WCRE'02: Proceedings of the ninth Working Conference on Reverse Engineering, pages 319-328, 2002. IEEE Computer Society Press.
[2] M. Di Penta, M. Neteler, G. Antoniol, and E. Merlo. A language-independent software renovation framework. Journal of System and Software, 77(3):225-240, 2005.
[3] T. Bodhuin, M. Di Penta, and L. Troiano. A search-based approach for dynamically re-packaging downloadable applications. In CASCON'07: Proceedings of the Center for Advanced Studies Conference, pages 27-41, 2007. ACM Press.

miniMAX Tool Set

miniMAX is a tool set that supports OdMoMs to perform software miniaturization. miniMAX help from requirements gathering to software generation. It divides into three tools: FacTrace, AURA, and a multi-objective optimizer, as shown in the following diagram.

Following is the detail of each tool.

FacTrace

FacTrace is a abbreviation of artefact traceability. FacTrace has several modules that help from requirement gathering to software miniaturization. FacTrace aids in software engineers in different tasks, namely, requirement elicitation, requirement analysis, artefact traceability, software reusability, and most importantly for software miniaturization. FacTrace has user-friendly graphical interface to perform different tasks. Following sections give you a brief description of different features of FacTrace:

Project Management (In Progress – Online version) FacTrace supports multiple project management. Each project can contain multiple datasets. For example, user can create miniaturization project and add email client and instant messenger datasets. FacTrace supports adding brief description of project. For example, project name and description. It supports adding, deleting, and exporting project details in CSV format.

User Management (In Progress – Online version) FacTrace supports teamwork. User can divide work and assign it to different users. For example, if you are working on requirement elicitation, you can assign some requirements’ labelling work to user A and user B while requirement analysis to user C.

Customer / Requirement Prioritization (A script but not integrated into FacTrace) FacTrace supports customer and requirement prioritization. User can assign different weights to customers or requirements for prioritization. FacTrace supports two weighting static and random. In static weighting, user can assign different weights to each customers or requirement. In random weighting, FacTrace automatically assign weights to users or requirements randomly.

Requirement Elicitation (Working – Online + Desktop version) FacTrace currently supports survey in English only to gather requirements. Users can write their requirement that will automatically be stored in database. Users can also upload their requirements in FacTrace specified XML format. FacTrace perform similarity analysis for all the elicited requirements. Similarity analysis helps users to see that if single customer or multiple customers wrote the same requirement twice. FacTrace supports exporting requirements into CSV and XML format.

Requirement Analysis (Working – Online version) FacTrace enables users to perform requirement analysis with easy mouse clicks. User can see all similar requirements and label them. User can write a label or simply click on a specific requirement; it will automatically be placed in text area to save user’s time. User can also categories each requirement as functional, non-functional, or outlier. User can categorize requirement as duplicate if user thinks the current requirement is somehow similar to other requirements in semantic. If any requirement is not been negotiated with customer, user can delete that requirement during requirement analysis.

Traceability Management (Working – Online + Desktop version) FacTrace aids in recovering traceability links between different software artefacts. For example, traceability links between requirements and source code. FacTrace allows users to create new links as well. It supports different level of granularity for creating traceability links. User can write description for each link and other identifiers specifications.

Traceability Links Voting system (Working – Online version) For avoiding biasness for traceability links, FacTrace supports voting system for each link. It supports up to 5 experts voting for each link. If three or more than three expert accepts a link, then a link will be considered as a valid link by FacTrace. Users can change their voting option at any time. All other experts’ voting is hidden to avoid biasness. Experts can see source code file in FacTrace source code viewer, to verify each link.

Requirement Elicitation / Traceability Reports (Working partially – Online version) FacTrace provides easy to understand tabular reports for requirement elicitations and traceability links. Reports can be exported in XML and CSV format. Reports are dynamic, it updates as soon as user make a change in the current project.

Requirement/ Traceability CSV/XML Export (In Progress) User can export all elicited requirements in CSV/XML format.

AURA

AURA [1] is a tool to identify framework evolution. It combines call-dependency and text similarity analyses in a multi-iteration algorithm to detect change rules from old versions to new versions of a program. It is able to automatically generate one-to-one, many-to-one, one-to-many and simply-deleted change rules. AURA includes a Model Builder which converts the source code a program to a language-independent model for further processing. For OdMoMs, the Model Builder of AURA is extended for the two tasks:

Source Code Dependency Manager (SCDM) Requirement traceability can trace to source code. However, it is quite possible traced artifacts are depend on other source code which are not directly related to the requirements. Dependency manager can built the dependency graph for all traced source code. It also supports XML dependency graph import and export.

Miniaturized Software Export (MSE) According to the solutions generated by the multi-objective optimizer (described later), MSE generates the miniaturize versions of the software that balance many its properties, such as code size and customers' satisfaction. The generated versions of source code are executable.

Multi-Objective Optimizer (MOO)

Let us describe MOO with an example of an Object-Oriented software system S. S includes N classes. In theory, any combination of the N classes can be a miniaturized version. In practice, many of them should be rejected because some of their properties, such as customers' satisfaction or code size, are not acceptable. Meanwhile, some of the properties essential to the miniaturized version are against each other. Keeping using customers' satisfaction and code size as example, normally, less code means less features and less customers' satisfaction which is that any software developer tries to avoid. MOO is a module applying multi-objective optimization algorithms on the system to be miniaturized to balance between contradict properties and to filter out unacceptable miniaturized versions, according to the constrains of the properties set by the developers.