Category: Software


By David Stites and Anitha Tadimalla {dstites, atadimalla}@uccs.edu
University of Colorado at Colorado Springs

Abstract— Mobile devices, such as smartphones and PDAs have become increasingly popular with consumers and often provide essential functionality in our everyday life. Usually these mobile devices contain lots of sensitive information, such as addresses, contacts, ingoing/outgoing call logs, SMS messages, and on latest models, a calendar, emails and potentially our current position. A smartphone or mobile device today is as powerful as a desktop or laptop and while the latest models feature a complete OS, for many users these devices are “just phones”, so there is a underestimation of the risk connected to mobile device security. This makes mobile devices an interesting target for malicious users. Damages that a user can sustain are financial loss, privacy and confidentiality, slowdown of processing speed, battery life.

Index Terms—mobile, security, malware, defense

  1. INTRODUCTION

Mobile devices, especially cellphones, have changed a great deal from their counterparts from the 1990s. Gone are the days of brick-sized phones, with a 1-line displays, 9 analog buttons and several KB of memory. In recent years there has been an explosion [2] of powerful mobile computing devices. These new smartphones and tablets, small enough to fit in your pocket or backpack, hold an immense amount of computing power. Information is available at a simple touch or finger flick and many users use these devices to access all sorts of data or services such as email, personal contacts, websites and even performing tasks normally reserved for a desktop system, such as video conferencing, watching movies or listening to music.

These devices are able to access the internet, download additional software from the internet, send and receive email, browse websites and send and receive SMS messages from other users. In addition to these capabilities, many subscribers use their cell phone as a primary method of communication, storing their personal contacts information (which include address, email addresses, phone numbers, etc.) as well as photographs they have taken. Additionally, many of these devices have a built-in GPS that allows the user to “geo-tag” photographs and use Location Based Services, such as FourSquare, Twitter and Facebook in addition to the basic mapping and GPS functionality.

Devices that run iOS (iPhone, iPad and iPod Touch), Android and Windows Mobile (which represent the majority of the market share) present a brand new computing paradigm in terms of availability, user interface and security. These devices are being targeted as never before by attackers [1]. Today more than 300 kinds of malware – among them worms, Trojan horses and other viruses and spyware have been unleashed against the devices [1]. Although desktop systems remain the most widely targeted platform, as mobile computing become more ubiquitous and powerful, the lines between a traditional desktop system and a mobile system will become blurred and these devices will gradually enter the virtual battlefield.

Clearly, these new capabilities mixed with the fact that users store personal information on the devices make it a prime target for attackers. There are three different basic categories of attacks that can be carried out against mobile devices and they include:

  • Confidentiality attacks: Data theft, data harvesting [3]
  • Integrity attacks: Phone hijacking [2]
  • Availability attacks: Protocol based Denial-of-Service attacks, battery draining [1]

These three categories represent a wide spectrum of security issues and there are many different attacks that an attacker could carry out. Any of the aforementioned attacks could range in severity from “low” to “high”, which makes this particular research area a wide open problem.

2. Survey Organization

This research paper is organized in the following manner: section III discusses some notable previous work that has been in this particular field, section IV discusses threats, vulnerabilities and defenses of mobile device security and sections V and VI presents some original work of the authors that show current and potential security threats to security from mobile device applications.

3. Previous Work

There has been a significant amount of previous work done in the area of mobile security. In [2], the authors show that since many of the mobile devices are based on similar codebases as their desktop counterparts (as in the case of Windows Mobile and iOS), rootkits, or stealthy malware that affects system programs and files, can equally affect the mobile version of these systems. In addition to showing that the systems can be exploited, they also show the implications of being able to compromise these devices.

In [4], the authors demonstrated the ability to deploy “a Trojan with few and innocuous permissions, that can extract a small amount of targeted private information from the audio sensor of the phone. Using targeted profiles for context-aware analysis, Soundcomber intelligently pulls out sensitive data such as credit card and PIN numbers from both tone- and speech-based inter- action with phone menu systems.”

In [5], the authors show that even though Android has an advanced permissions system with a sandboxed execution environment, a “genuine application [can be] exploited at runtime or a malicious application can escalate granted permissions and imply that Android’s security model cannot deal with a transitive permission usage attack and Android’s sandbox model fails as a last resort against malware and sophisticated runtime attacks.”

In [3], the author shows many of the attacks that occur on iOS have to do with theft or procurement of personal or private information. For example, iOS applications would have access to a user’s address book that includes phone numbers, addresses and email addresses. Additionally, an application can also access other data such as call history, carrier information and photographs.

4. Threats, Vulnerabilities and Defenses to Mobile Device Security

A) Attacks and Vulnerabilities

Since there has been explosive growth in the mobile device market and the demand for smartphones, tablets and other integrated devices have increased dramatically. According to Nielsen [5], “in the third quarter of 2009, smartphones accounted for 40% of new phones sold in the period, up from 25% in the prior quarter. And in the third quarter, for the first time, more people accessed the Internet from smartphones than regular phones. Assuming that 150 million people will be using smartphones by mid-2011, that means 120 million will be on the mobile Internet and 90 million, or 60%, will be watching video” according to Nielsen projections based on current data trends.

In addition to a enormous user base, people are spending more time on their mobile devices than ever before. “As of the second quarter, Nielsen has previously reported that some 15 million U.S. mobile subscribers watch video on their phones for an average of three hours, 15 minutes each month” [5].

Previously attacks such as the ones detailed later in this section haven’t been seen until now. Securing mobile devices present unique challenges to researchers, attackers, defenders and users. This “uniqueness” is due to the fact that computers don’t typically have some the interfaces that mobile devices do, such as GPS hardware, or similar data storage paradigms, such as storage in the cloud. Several potential reasons mobile malware and attacks are becoming more popular is because people are using their mobile devices for more day-to-day tasks such as banking, email and web surfing. This might cause users to store more “valuable” information on these devices and this represents a prime target for attackers due to the wealth of information they could obtain. In addition, while users may have good security habits when it comes to more traditional systems, they may not realize that their mobile device could be just as vulnerable as their servers, desktops and laptops.

I) History and Current Day Data

The first known cell phone virus, Cabir (EPOC.cabir and Symbian/Cabir), occurred in 2004, written by the group 29A [1, 8]. It affected devices that had Bluetooth modules and spread using Bluetooth via OBEX (object exchange). While it was originally designed as a proof-of-concept that would affect Symbian OS devices, it could spread to any Bluetooth enabled device such as desktop computers and printers.

The virus would activate each time the phone was turned on and immediately start looking for other hosts to infect. However, Cabir required the victim user to accept the transfer before any transfer could start. If an attacker were able to masquerade as someone the victim trusted, then they could easily socially engineer their way into infecting the victim’s phone.

Since the virus was released as a proof-of-concept to shock the security community into focusing on the importance of mobile malware, it did nothing other than drain the battery of the infected device while it constantly scanned for new targets to which to send the virus. A variant of Cabir, Mabir, was released that infected phones not only via Bluetooth but also by SMS, so it could use the carrier as an attack vector. This increased the infection potential of this virus exponentially since you didn’t have to be within the 10 meter range of Bluetooth to be infected.

Other historic, notable mobile malware include Duts (a virus for the PocketPC platform), Skulls (a trojan horse that infects all applications, including SMS/MMSes) and Commwarrior (a worm that used MMS messages and Bluetooth to spread to other devices). A more complete list of mobile viruses, trojan horses, worms and malware exist at [1, 7, 8].

Clearly, since mobile devices represent the future of computing, the fact that mobile malware is becoming more prolific shouldn’t be a surprise. In fact, F-Secure reported an almost 400% increase in mobile malware within a two year period from 2005-2007 [2].

Additionally, [9] reports that the amount of Android malware jumped 37% in the third quarter of 2011 and that Android is now the “exclusive platform for all new mobile malware. While the Symbian OS remains the platform with the all-time greatest number of malware, Android is clearly today’s target.” Today, there are currently over 1,200 known malware samples [9].

In [10], the authors performed a survey of mobile malware in the wild. They determined, that between 2009 and 2011, there were 46 pieces of malware released, including 4 for iOS, 24 for Symbian and 18 for Android. They also determined that the most common malicious activities were confidentiality attacks (collecting user information, 61%) and integrity attacks (sending premium-rate SMS messages, 52%).

I) Reasons for an increase in attacks

There are a number of reasons that the community is now experiencing an increase in malware including:

  • Increased computing power and storage capabilities: While many consumers may not recognize mobile devices as being equivalent in power to their larger counterparts (laptops and desktop PCs) due to their size, many smartphones, tablet devices and other PDA type devices have a rich set of hardware interfaces. Many smart phones, such as iPhones, Android-based phones, have powerful dual-core processors and a large amount of storage space to accommodate music, movies, documents and other types of media that can be consumed on the go.

In addition, the available software applications that come pre-installed on the device by the device manufacturer, such as web browsers, email clients, messaging applications allow the user to interact much more with the physical and virtual world than previous mobile devices. Furthermore, additional software applications can be downloaded, installed from the Internet and run by the user. These third-party applications are able to access this advanced hardware as well as GPS and network interfaces (3G, WiFi and Bluetooth).

This provides mobile malware and crimeware authors a much larger array of possibilities to carry out their attacks. In addition, more sophisticated hardware and software could make it easier for these attackers to “hide” their attack by ensuring that it only consumes a small portion of the resources, thereby modeling a legitimate application.

  • Increased network connectivity: There is a widespread availability of 802.11 WLANs and high-speed broadband data access (3G, WiMAX). These services allow users to stay constantly connected to services such as email and messaging at home, at work and in foreign places, such as coffee shops. In addition, many applications utilize network connections to either request or send data. For example, a game application might transmit a user’s high score to a web server for storage.

Additionally, some applications rely on the fact that the phone will have a network connection to receive and send data, such as the Amazon.com shopping application. Lastly, many recent applications utilize location-based services, such as Facebook, Twitter, and FourSquare. These applications provide additional functionality if they are able to access the network and a user’s current location.

Lastly, many applications can make use of social data, such as the friends one might have on Facebook. This Facebook data could be stored within the application. While Facebook might maintain rigorous security standards on who and what can access the user’s data, other third party applications might not be so careful with the user’s data.

  • Standardization of OS and interfaces: The OS is consistent on all the same family of devices, so malware applications would have more effect, being able to exploit the same security vulnerability across many devices. In addition, many manufacturers give third party developers access to the system to write applications for the platform. For example, one can freely download the Android and iOS SDK. Using this provided SDK, one could craft a virus or some other piece of malware and then submit it for inclusion in the respective application storefronts.
  • Enterprise integration: Many mobile devices, such as Android, iOS and Blackberry, support standards to be integrated into an enterprise environment. For example, many of the same devices have support for Virtual Private Networks (VPNs) as well as Exchange server integration. Thieves and malware authors recognize that this will greatly enhance the infection potential if a mobile virus, trojan horse or worm is able to spread from a mobile device to a corporate environment.

Consider the case of an employee with a mobile device becoming infected while at a coffee shop and taking that device back to the corporate environment where it could spread throughout the organization. Where previously an attack might have only stolen information pertaining to the particular victim, now the attacker could have potentially obtained information on many different people as well as corporate information.

  • Other reasons, social engineering and hacktivism: The number of socially-engineered attacks are becoming more prevalent and more sophisticated. [9] reports “that targeting content works based on cultural and sociological differences between geographic regions. Hacktivism have become part of the mainstream in 2011 due to groups such as Anonymous and LulzSec.”

I) Attack Vectors, Motivations and Types of Attacks

There are a number of attack vectors that exist for compromising confidentiality, integrity or availability. In fact, many of the attack vectors are the same ones that are available to desktop applications. Mobile attack vectors often spread via interfaces and services as well as interfaces unique to smart phones, including SMS and MMS.

While the motivation behind such attacks can be varied and numerous, as well as being outside the scope of this paper, [10] identifies some current and future incentives including:

  • Novelty and amusement
  • Financial Gain
  • Political Gain
  • Damage resources

In addition to numerous attack vectors and motivations, there are many different types of attacks that a malicious individual could attempt to carry out. [10] defined three main categories of attacks including 1) malware attacks 2) grayware attacks and 3) spyware attacks.

Malware attacks: “Malware attacks are attacks that gain access to a device for the purpose of stealing data, damaging the device, annoying the user, etc. The attacker defrauds the user into installing the malicious application or gains unauthorized remote access by taking advantage of device vulnerabilities. These particular types of threats provide no notice to the user and typically includes worms, Trojan horses and viruses [10].”

  • RF attacks: In this particular type of attack, an attacker could compromise confidentiality, integrity and availability. For example, if an attacker were to have the correct equipment, the attacker could sniff the air (WLAN and RF) for user data that the attacker could steal if it were unencrypted, such as usernames, passwords and account numbers. This particular type of attack is made easy if: 1) the network the user is on doesn’t utilize encryption and, 2) the application transmits confidential information in plaintext.

As we’ll see later on in section V, there are a number of iOS applications today that transmit private information without encryption. Additionally, if an attacker were able to successfully carry out a “mis-association” attack where the mobile device joins the wrong access point, the attacker could attack the integrity of communications by performing a “man-in-the-middle” attack, if the data were not validated or signed. Consider an example where a victim user sent a SMS message that said “Transfer $1000 to account X.” The attacker could alter the SMS to say “Transfer $10,000 to account Y”, where Y was his account.

Lastly, an attacker could also compromise the availability of RF services. Consider an example where an aircraft was WiFi enabled (passengers could access the WiFi during flight). An attacker could carry out a “disassociation” attack, where he transmits 802.11 management frames that cause the wireless clients to disassociate from the access point. The denial-of-service would continue until the attacker stopped transmitting the packets.

  • Bluetooth attacks: This particular class of attack has many different possible different attacks, similar to RF attacks, that can compromise confidentiality and integrity of data. In “blue-jacking”, an attacker’s malware application could insert contacts or SMS messages into a victim user’s mobile device. Additionally, in “blue-snarfing”, a user’s data is again under attack by allowing the attacker to steal or transfer the victim’s data. Yet another type of bluetooth attack is “blue-tracking” where an attacker could follow the victim’s movements. Lastly in “blue-bugging”, an attacker could listen in on conversations by activating the attack software and having the phone call them back. When the attacker answers the call back, the attacker would then be able to listen in to a conversation.
  • SMS attacks: “SMS spam is used for commercial advertising and spreading phishing links. Commercial spammers are incentivized to use malware to send SMS spam because sending SMS spam is illegal in most countries” [10]. In addition to sending and receiving regular-rate SMS messages, SMS can also be used as an attack vector by exploiting vulnerabilities in the software stack, such as performing SMS fuzzing.
  • GPS/Location attacks: In this type of attack, the attacker can access the GPS hardware to monitor the user’s movement and current location. This data can be used to create a profile of a particular user. In addition, this information could be sold to to other companies for purposes of marketing and sending advertisements to the user. A more insidious use of a GPS/location attack would allow a criminal to track when a victim leaves their residence and then the attacker could rob the person while they are gone.
  • Application masquerading and personal data attacks: This particular type of attack is as simple as accessing a user’s private data and saving, sending or using it in an unauthorized manner. For example, in [3], the author shows multiple examples of information that an application could access that could potentially be sensitive or confidential, such as a user’s phonebook, keyboard and location cache and photo albums.

In addition, [3] also showed that it would be relatively trivial for an application to traverse the file system of a mobile device, recording information that it could find valuable. This can all occur in the background and the user would never know that it is happening. This data could be sent off to a server and stored for later misuse.

  • Phone “Jailbreaking” and 3rd party application stores: While not encouraged by the manufacturer, (and in some cases against the carrier terms and agreements), many users prefer to “jailbreak” their mobile devices. Jailbreaking is the process of removing the security limitations that are imposed by the operating system, such as the ability to only run signed applications and install additional extensions and themes. This also allows the user to bypass application sandboxing mechanism and install applications from unofficial application stores. Users find this desirable because they can add functionality that didn’t previously exist or could get from any existing application on the application stores. However, users may not realize that this could potentially be a problem if they were to install a malicious application that would normally be killed by the OS on an un-jailbroken device. For example, one of the available exploits for iOS is when a user jailbreaks their iDevice, installs the OpenSSH package and doesn’t change the root password for the device, which is “alpine”. This would allow a hacker to login to their device as the root user and exploit the system because they would have full access to read, write and execute any command.
  • Premium-rate attacks: Premium rate services can deliver valuable content to a user’s mobile device. When used in a legitimate manner, a user could receive financial information, technical support or even adult services. These services can cost as much as several dollars per message or minute. In [10], they identified 24 of the 46 pieces of malware surveyed as sending premium-rate SMS messages. In one piece of malware, [10] found that applications purporting to be a Russian adult video player sent premium-rate SMS to an adult service.

Another piece of malware, Geinimi, sent premium SMS messages to numbers specified by the remote command servers. This is potentially a very large security concern, because these premium SMS messages don’t require a user’s permission to send, so they potentially could go unnoticed until an attacker has racked up hundreds or even thousands of dollars on a victim user’s phone bill. In addition to premium-rate SMS message attacks, [10] also found that 2 of the 46 malicious applications contained premium-rate phone call attacks.

  • Power management attacks: [11] describes three different classes of power management attacks. A power management attack is a form of a denial-of-service attack that affects the availability of the mobile device by draining the battery more quickly than it would under normal operation. The attacker’s goal is to maximize the difference in power consumption between active and sleep states and keep the device from sleeping.

The three classes of attacks include 1) service request attacks 2) benign power attacks 3) malignant power attacks. In service request attacks, repeated requests are made to the victim for services, typically over a network. Even if the request is ultimately not granted, the power must be expended by the device to determine whether or not to grant the service request. In benign power attacks, the mobile system executes valid, but power hungry tasks (such as displaying a hidden animated gif or executing a JavaScript). In malignant power attacks, attackers create or modify binary executables that force the mobile system to consume more power than it normally would. For example, consider an application that plays a silent audio track in the background while the application is running. This type of attack might be difficult for the user to detect because they may think that their battery can no longer hold a charge.

  • Time-activated and location-activated attacks: An attacker may choose to activate attacks at certainly locations or at a pre-determined or random time in the future. When the victim arrives at the location and uses the software, it could activate whatever is the intended malignant function. This would be fairly easy to do as many applications have access to the GPS. This type of attack may also sneak by any analysis of the application as it wouldn’t run every time the application was launched, but rather only under certain conditions.

In addition to malware attacks, [10] also defines several other types of “attacks” including:

Grayware attacks: In [10], the authors classified grayware attacks as “some legitimate applications collect user data for the purpose of marketing or user profiling. Grayware spies on users, but the companies that distribute grayware do not aim to harm users. Pieces of grayware provide real functionality and value to the users. The companies that distribute grayware may disclose their collection habits in their privacy policies, with varying degrees of clarity. Grayware sits at the edge of legality; its behavior may be legal or illegal depending on the jurisdiction of the complaint and the wording of its privacy policy. Unlike malware or personal spyware, illegal grayware is punished with corporate fines rather than personal sentences. Even when the activity of grayware is legal, users may object to the data collection if they discover it. Application markets may choose to remove or allow grayware when detected on a case-by-case basis.”

For example, in 2009, bloggers raised concern over the PinchMedia LLC analytics framework. This framework provided third party application developers usage information about their users. The users were not informed and they were not given an option to opt-out [3]. In addition, Storm8 and MogoRoad also faced legal issues when it was discovered that they were collecting users’ contact information without informing them and then transmitting the collected information in plaintext [3].

Spyware attacks: The last category that [10] detailed was “Spyware attacks.” “Spyware collects personal information such as location or text message history over a period of time. With personal spyware, the attacker has physical access to the device and installs the software without the user’s knowledge. Personal spyware sends the victim’s information to the person who installed the application onto the victim’s device, rather than to the author of the application. For example, a person might install personal spyware onto a spouse’s phone. It is legal to sell personal spyware in the U.S. because it does not defraud the purchaser (i.e., the attacker). Personal spyware is honest about its purpose to the person who purchases and installs the application. However, it may be illegal to install personal spyware on another person’s smartphone without his or her authorization [10].”

For more on platform specific exploits, in the papers we surveyed, please reference [1, 2, 3, 4, 6, 10, 11, 18, 20].

A) Defenses

When defending against mobile phone security threats and mobile malware, there are two main categories: prevention and detection and recovery. The majority of the work that has been already implemented falls into the class of prevention. However, detection and recovery is becoming a more popular research topic. We discuss some of the major defenses below:

  • Code analysis (static and dynamic): There are two main techniques of determining an application’s characteristics: statically and dynamically. Both have certain advantages and disadvantages.

In static analysis, many techniques may be used to determine how the program works, such as decompilation, decryption, pattern matching and static system call analysis. The central idea behind static analysis is finding signatures of malicious code in a fast and easy manner. In [3], the author describes part of the App Store review process for applications and detail that using static analysis, one can dump the strings in a binary file and check them against a black list of forbidden classes, method names and file paths. However, static analysis can be circumvented with obfuscation techniques. Additionally, some languages, such as Objective-C allow developers to lookup classes and methods by name at runtime. This feature of the language adds additional opportunity to “hide” malware functionality.

The primary disadvantage of static code analysis is that malicious code patterns have to be known in advance, making it impossible to automatically detect new malware or malicious polymorphic code without an intervention of a human expert [23].

Dynamic analysis is a set of techniques which involve running an application in a controlled environment and monitoring its behavior. Various heuristics can be used to capture behavior of the application such as monitoring file changes, network activity, processes, threads and system call tracing [23].

One large difference between the iOS App Store and the Android Marketplace is that applications that are released to the iOS App Store are reviewed by a human. This accomplishes an important goal in that it rejects applications that are in a “legal gray zone such as casino gambling or collecting personal data.” The Android Marketplace allows an author to post apps without needing any a priori review but rather it relies on “crowd-sourcing” to review the applications and post comments, either positive or negative.

  • ASLR and DEP: ASLR (address space layout randomization) is a computer security method that involves re-arranging the positions of key data areas, including the position of libraries, the heap and the stack in the process’ address space. This technique makes it more difficult for an attacker to predict target addresses [21]. For example, an attacker who is attempting to overflow the stack, would first have to locate the address of the stack before they could overflow it. If an attacker were to guess incorrectly and the program terminated, the next time the program were launched, the stack address will have moved again and the attacker would have to start all over again in their attempt to find it. While the full description of how ASLR is implemented and its effectiveness is outside the scope of this paper, the reader may learn more at [21].

In addition to ASLR, DEP (data execution prevention) is another security feature that prevents an application or service from executing code from a non-executable memory-region. This protection can be enforced in hardware and/or software. Again, while the full description of how DEP is implemented and its effectiveness is outside the scope of this paper, the reader may learn more at [22].

The platforms that support ALSR and DEP include iOS and Windows Mobile. Android has plans to support ASLR but the Blackberry platform has neither.

  • Application sandboxing: “Sandboxing consists of running mobile code in a restricted environment called a sandbox [17].” A sandbox can be characterized by two different mechanisms: 1) confining code, either through type checking, language properties or the use of protection domains to prevent the subversion of trusted code and 2) enforcing a fixed policy for the execution of code [17].

When applied to the real world, each application will have its own environment. Other applications should not be able to interfere with another applications environment nor should that particular application be able to interfere with other applications’ environments. Both iOS and Android implement application sandboxes. In the iOS model, each application only has read-write access to a few directories (the application’s own directory and a temporary directory) and applications cannot read or write to any other directories (including other applications and system directories) than for which it is authorized.

In the iOS sandbox, all applications share the same sandbox rules and they’re allowed any action any application could ever need [18]. Compared to the Android sandbox, “applications must explicitly share resources and data and do this by declaring permissions they need for additional capabilities not provided by the basic sandbox. These additional permissions are granted or denied by the user at install time only. [13]”

  • Permission systems: In Android, there is the additional protection of a permission system. This permission system “treats all applications as potentially buggy or malicious so they are assigned a low-privilege ID that can only access their own files [19].” Depending on what the application wants to do, it can request an elevation of permissions from the user, at install-time, which the user will ultimately grant or deny.

For example, there are several different levels of permissions including Normal (permissions that protect access that could annoy but not harm the user, such as setting the wallpaper), Dangerous (permissions that protect access that potentially harm the user such as gathering private information), and System (permissions that need access to the most dangerous privileges, such as deleting applications).

In addition to the permissions system, Android also has the Intents system. Intents are typed interprocess messages that are directed to particular applications or systems services, or broadcast to applications subscribing to a particular intent type [20]. Access to the Intents system is funneled through ActivityManagerService which restricts intents only being sent by applications with the appropriate permissions and processes with a UID that match the systems [19].

iOS does have a rudimentary concept of a permissions system but not one that is as in depth as the Android model. For example, when an application attempts to access the user’s location via the GPS hardware, the application will confirm with the user that this is an acceptable action, which the user can confirm or deny. However, for the most part, Apple relies on a number of other techniques to handle security issues, such as Sandboxing, ASLR/DEP and code analysis.

  • ACLs and capability lists: Both iOS and Android implement standard UNIX type permissions with users and groups. This allows the systems to implement the concept of “least privilege” where accounts and users are only able access data to which they are properly privileged to access. In iOS, files have permissions and third party applications runs as the user “mobile”, instead of root. In addition, certain operations on Android require the proper permissions, such as accessing as network interfaces. Typically, when a user “roots” or “jailbreaks” their device, they are elevating the permissions of the application to that of a more privileged account to bypass certain security features such as sandboxing.
  • Code signing: Code signing is a process where executable binaries are signed digitally by software authors to guarantee that the code that has not been altered or corrupted [15]. This is an important part of the defense systems in both the Android, Blackberry, Windows Mobile and iOS security model and it is used extensively in both models for validating third party applications. An important distinction between the two is that with iOS code signing, the code must be signed with a certificate validated by a certificate authority or CA (in this case, Apple), whereas with Android, self-signed certificates are acceptable [13, 14]

In addition to validating applications, iOS also uses code signing when booting up. When a device running iOS boots up, the first significant piece of code that runs on a device running iOS is the BootROM or the “SecureROM”, which is read-only [16]. Within this BootROM, an Apple root certificate is embedded such that the firmware can be validated as being official and secure. Once the RSA signature has been checked, control is passed to the low level bootloader or the “LLB.” This module runs several setup routines and checks the signature of iBoot, which is a stage 2 bootloader for all devices running iOS. Once iBoot starts, it allows the device to go into a “recovery” or “DFU” mode that allows devices to be restored from any state. Firmware images from Apple are signed and checked when the upgrade or downgrade occurs. If the device boots normally instead of going into DFU mode, control is passed to Launchd, CommCenter, and Springboard [11].

In addition to validating system software, iOS also signs the code directory structure with SHA-1 hashes of memory pages, and a PKCS#7 signature is embedded in all binaries that are downloaded from the App Store [11]. For binaries that do not validate at run time, they are killed by the OS to prevent any binary that has been altered from running. Lastly, to provide a defense against rootkits, for system binaries, code directories hashes are cached in the kernel [11].

While regular users may not know or care whether a binary is signed properly, this particular process creates accountability and increased trust on the platform if an application can be traced back to a known source.

The astute reader will recognize that a signed binary may not necessarily contain safe or bug-free code – just code verified as coming from a particular known source and has not been subject to tampering. Also, if the system does not strictly enforce running only validated binaries, users could be tricked (through social engineering perhaps) into running code that refuses to validate. Lastly, one potential flaw with Google’s scheme is that Google does not require that a CA sign the application signing certificate – they only record the signatures for book keeping purposes. This additional level that Apple introduces could potentially reduce the amount of malware and spyware on Android.

  • Data encryption: Data encryption and decryption is a very CPU and power intensive activity. Battery life on a mobile device is a very precious commodity because the usage model for a mobile device is such that the devices are meant to be used out in the field where a constant power source isn’t always available. As such, there hasn’t been any commercial implementations of automatic whole disk encryption. However, certain OSes, such as iOS, encrypts particular items such as the Keychain (a password manager and storage framework) and provides the ability to encrypt individual files. Another option for third party applications is to provide their own encryption services framework, using known models, such as PKI, and known programs, such as OpenSSL.

One interesting study of mobile device encryption was done by the authors of [28]. In their research, they explored the use of Field Programmable Gate Arrays or FPGAs, processors and ASIC hardware in the context of finding a framework for encryption on hand-held communication units. They used the IDEA encryption algorithm to show the tradeoffs in the suggested technologies. They measured their results using three different metrics: 1) performance, 2) programmability and, 3) power consumption. They determined that since power consumption is directly related to frequency, FPGAs provided the highest performance (MOPS/watt).

  • Detection and recovery defenses: There has been a lot of notable work done in this category of mobile malware defense. For example, [24] presented various approaches for mitigating malware on mobile devices. The authors implemented and evaluated the suggested approaches on Google Android. The work is divided into the following three segments: a host-based intrusion detection framework; an implementation of SELinux in Android; and static analysis of Android application files.

[24] determined that to provide well-rounded protection, a security suite for mobile devices or smart phones (especially open-source ones such as Android) should include a collection of tools blending various capabilities that operate in synergistic fashion.

In [24], the author’s first approach was an innovative host-based intrusion detection system (IDS) for detecting malware on mobile devices. This framework relies on a lightweight agent (in terms of CPU, memory and battery consumption) that continuously samples various features on a device, analyzes collected data using machine learning and temporal reasoning methods and infers the state of the device. Features belonging to groups such as Messaging, Phone Calls and Applications belong to the Application Framework category and were extracted through APIs provided by the framework; features belonging to groups such as Keyboard, Touch Screen, Scheduling and Memory belong to the Linux Kernel category.

This study on anomaly detection was based on various detection algorithms. The purpose of this study is to understand how a detection algorithm, a particular feature selection method and number of top features can be combined to differentiate between benign and malicious applications which are not included in the training set, when training and testing are performed on different devices and to find specific features that yield maximum detection accuracy. Empirical results suggest that the proposed framework is effective in detecting malware on mobile devices in general and on Android in particular (accuracy of 87.4% with false positive rate of 12.6%).

The author’s second study examined the applicability of detecting malware instances using a light version of the Knowledge-based Temporal Abstraction (KBTA) method that can be activated on resource-limited devices. The new approach was applied for detecting malware on Google Android powered-devices. Evaluation results demonstrated the effectiveness of the new approach in detecting malicious applications on mobile devices (detection rate above 94% in most scenarios) and the feasibility of running such a system on mobile devices (CPU consumption was 3% on average).

This study also proposed the implementation of SELinux in Android in order to harden the Android system and to enforce low-level access control on critical Linux processes that run under privileged users. By choosing this route, the system can be better protected from scenarios in which an attacker exploits vulnerability in one of the high privileged processes.

[25] is another interesting study using malware behavior detection. This paper proposed a behavior-based malware detection system for Windows Mobile platform called WMMD (Windows Mobile Malware Detection system). WMMD uses API interception techniques to dynamically analyze an applications behavior and compare it with a malicious behavior characteristics library using model checking.

The architecture of the proposed framework consists of two modules: a Dynamic Analysis Module and a Behavior Detection Module. Both modules use the API interception technique to obtain software running information. The Dynamic Analysis Module is responsible for analyzing the program’s behavior. The Behavior Detection Module monitors the process’ real time information and compares it with abehavior signature library. Once it detects a mal-behavior, it responds to the user and offers a feedback to construct new behavior model.

All the experiments were done first in Windows Mobile Emulator in PC and then verified in a real mobile phone. The Emulator is Windows Mobile 6.0 professional version and the real mobile phone is HTC PPC6800 with Windows Mobile 6.0 OS.

To test WMMD’s effectiveness towards obfuscation or packing techniques, they used UPX packer to pack five Windows Mobile viruses, and compare WMMD to six other anti-virus software packages (Windows Mobile 6.0) which included an updated virus signatures database. Testing results revealed that all of the other anti-virus products can only detect the virus before packing and they are useless when the virus was packed. However, the WMMD can detect those viruses after packing, since WMMD checks the API call in real execution which cannot be changed. For example, WinCE.Infojack.A is a trojan that binds to popular software installation files and it will extract a file named mservice.exe to the \Windows directory and create mservice.lnk file to the \Windows\StartUp directory. It then start this mservice.exe process. It is apparent that other variants of WinCE.Infojack.A have the same behavior and thus they only need to monitor the CreateFile() and CreateProcess() APIs to check whether their arguments satisfies the specific behavior.

This evaluation on real-world mobile malware shows that behavioral detection can successfully detect malware variants which have certain behavioral patterns with existing patterns in the database, while other anti-virus product cannot detect.

In [26], the authors describe that malware doesn’t always need to be physically installed on the phone to affect the mobile device as they considered defending mobile devices against “proximity malware.” The dynamics of proximity propagation inherently depend upon the mobility dynamics of a user population in a given geographic region. Unfortunately, there is no ideal methodology for modeling user mobility. Traces of mobile user contacts reflect actual behavior, but they are difficult to generalize and only capture a subset of all contacts due to a lack of geographic coverage. Analytic epidemiological models are efficient to compute and scale well, but simplify many details. Synthetic models are flexible and provide the necessary geographic coverage, but lack the full authenticity of user mobility traces.

[26] assumed that devices have a trusted defense software component that can examine messages and files transferred between devices, securely record persistent information about these transfers, and control device hardware when necessary (e.g., disable radio communication). These assumptions may be strong, but not unreasonable given the increasing prevalence of trusted computing modules. However, if malware has the ability to disable defense software, we can predict what the result will be: unchecked propagation through a population.

The first strategy described in [26] simply uses local evidence to detect malware and prevent further dissemination by the device, such as by disabling the Bluetooth or WiFi radio. Preventing further propagation by disabling communication may inconvenience the user, but voice and messaging with the provider network remain possible. Disabling the malware prevents further propagation but makes no attempt to notify other devices or the network about the presence of malware. It serves as a useful baseline for comparison.

The second strategy described in [26] extends local detection with an active mitigation component. In this strategy, each device maintains a table S of signatures of malware files, such as an MD5 hash over the file content. After a device X infers that it is infected, it disables the malware and warns subsequent devices about it. Device X computes a content-based signature s over the file(s) that triggered the infection recognition (e.g., the hash it has used to track file transfers in the first place). When X comes into proximity contact with another device Y, X disseminates the signature s to Y . If Y is infected, it immediately disables the malware. Y then adds s to its signature table S. Whenever another device shares a file with Y, Y will check the file against the signatures in S. The device can then either delete the file, or warn the user about the file.

The third strategy described in [26] relies upon the network provider to disseminate signatures using a broadcast mechanism. In addition to standard unicast messaging, providers are also able to send data packets over broadcast at a low cost. In this strategy, whenever a device decides that it is infected, it sends the malware content to an anti-virus server in the provider network (using MMS). The server, since it presumably contains far greater processing power than the mobile devices, can compute a better quality signature. Also, due to access to anti-virus experts, the server may also be able to compute a patch that contains information on how devices may “cure” themselves and remove the infection from the device. Manual involvement in generating patches is also a possibility.

Lastly, in [27], the authors used data mining techniques to detect malware behavior. This paper proposed a technique of ontology-based behavioral analysis to develop a detection method for smart phone malware. In this experiment, a mobile environment is constructed in the laboratory. The HTC HD2 smart phone with Windows mobile 6.5 operation system was adopted as the main test platform. Then they installed and ran their mobile malware detection system (MMDS) on an HTC HD2 smart phone. Then the other smart phones sent files or messages to the HTC HD2 through MMS or SMS. The MMDS can automatically filter all files and message by extracting their behavioral characteristics. The system will determine the degree of danger of these behaviors. When users have confirmed that this message is in danger of intrusion, the system will refuse the MMS or SMS.

As a result of the experiment in [27], the proposed FPN model can detect most of new mobile malware. However, there exist two pieces of mobile malware that cannot be detected by the FPN model. Since the collection of mobile malware is difficult, one cannot gain various types of mobile malware to test. Thus, the FPN model through the behavior analysis of mobile malware based on the ontology theory may not detect the above-mentioned mobile malware.

I) Future Defense Work

The authors would also like to explore the feasibility of implementing other security features such as:

  • Enhanced permissions systems: It would be worthwhile to spend time researching how one could detect over-privileged applications and adjust their privilege level for only the privileges that are needed. Additionally, research into a permission models that allow finer-grain control on application permissions would allow developers and users to control exactly what information or modules could be used or accessed. Lastly, research into dynamic analysis models to determine malicious activity would be useful as mobile platforms and applications are becoming more complicated and future attacks could possibly target push notification systems and in-application purchasing systems.
  • Trusted computing modules: Trusted computing is a technology that ensures that a computer will consistently behave in an expected way and that those behaviors will be strictly enforced by hardware and software. If these modules could be included as hardware on the phone, we could ensure that hackers couldn’t deploy rootkits on phones because the boot process would be verified and secure.
  • Encryption modules: Many desktop operating sytems implement some form of full hard drive encryption, such as Windows BitLocker and Mac OS X FileVault. Using a hardware encryption module, it would be possible to encrypt the entire hard drive without consuming a large amount of battery power. For example, the user application space could be encrypted in a separate volume that is mounted and decrypted at boot time. In addition to encrypting the entire user application space, applications could also provide their own separate encryption keys to do encryption of application specific data.
  • Firewall modules: Since smartphones and mobile devices are now as powerful as desktop computers, and the trend of consumers using them as a replacement to desktop and laptop systems will continue, more personal and confidential data will be stored on mobile platforms. It would be valuable to invest research time into mobile firewalls and packet filtering in attempt to possibly detect whether or not data harvesting is occuring on the device and being transferred across a network interface.

5. Applications Survey

The author surveyed over 230 applications (the full list of applications ,can be found in Appendix A), including applications in the “Top” categories on the iTunes store to determine what type of information could be extracted from auditing packet streams. The results were quite surprising.

To perform this audit, the author launched one application at a time and used WireShark to capture and analyze packets. The experiment was performed on an open network that the author created. The access point was a Cisco Small Business router (WAP4410N) and was configured using a hidden SSID and MAC address authentication to prevent outside users from associating with the access point and introducing outside, extra packets. While the author realizes that hidden SSIDs and MAC address authentication are easily defeated mechanisms, it was used to prevent casual users from using the access point. The mobile devices used were an Apple iPod Touch 4G, an Apple iPad 1G and an iPhone 4, configured with iOS 5.0.1.

For reasons of classification, the authors created several different levels of potential security breaches. The levels are defined as:

  • None: This level is defined as having no potential security breaches and no exposure of confidential information.
  • Low: This level is defined as having a few potential security breaches or exposure of confidential information that could not directly affect the user, such as device IDs that could be used in tracking users (in iOS, these are called UUIDs).
  • Medium: This level is defined as having several potential security breaches or exposure of confidential information that is potentially serious or if information is exposed such that an attacker would be able to identify the user on an individual basis, such as addresses, latitudes or longitudes, etc.
  • High: This level is defined as having multiple potential security breaches or exposure of extremely confidential information, such as account numbers, PINs, and username/password combinations.

For more information on the specific application, including the version number of the application with the vulnerability, see Appendix A for a full listing.

Application

Level

Risks Found

GrubHub

Low

UUID

The Weather Channel

Low

Geocoded location

Path

Low

UUID

Handmade

Low

UUID

iHeartRadio

Low

Reverse Geocoded location

TabbedOut

Low

UUID, Platform

Priceline

Low

UUID, Geocoded location, “Search” API is unencrypted

Free WiFi

Low

Geocoded location

Coupious

Medium

Geocoded location, UUID, coupon redemption codes

Delivery Status

Medium

UPS transmits reverse geocoded locations and tracking numbers.

Color

Medium

Reverse geocoded location and photos taken and shared by users

Cloudette

Medium

Username in plaintext and password, hashed with MD5

Gas Buddy

Medium

Username and password, hashed with MD5

Ness

Medium

Reverse geocoded location

Southwest Airlines

High

Username and password in plaintext

Minus

High

Username and password in plaintext

WordPress

High

Username and password in plaintext

Foodspotting

High

Username and password, Geocoded location

ustream

High

Username and password, UUID, geocoded location

Labelbox

High

Username and password, geocoded location

The majority of the applications that were surveyed encrypted the exchanges of confidential or sensitive information, such as usernames, passwords and account numbers via SSL/TLS.

However, many applications performed some sort of tracking or storing of analytic information, such as passing the UUID in a call to a web service. In some of the instances, this identifying information was not encrypted. While not potentially dangerous in the sense that an attacker could use this information to “identify” a particular person, none of the applications let users know that their information such as UUID, phone OS and model, was being used or recorded, nor did they let the user “opt-out.”

The largest single potential security breach was with the Southwest Airlines application. Due to the fact that the username and password were submitted to a web server via a POST operation in plaintext, an attacker could simply sniff for this data. If an example was captured, one could use those credentials to log into a particular account and book travel, use award miles and possibly change information in the victims profile. This not only obviously worrisome from the standpoint of a potential attacker fraudulently using a victims account and credit card information, but also due to the possibility of a terrorists threats in air travel.

For example, consider the possibility of a person who is currently (and rightfully) on the Department of Homeland Security’s “No-Fly” list. If this person were able to capture a victim’s credentials and create a fake ID, he could pass through TSA security without being stopped.

Of the 253 applications surveyed, 91.7% had no risk found, 3.1% had a low risk, 2.3% had a medium risk and 2.3% had a high risk. While it would be desirable to have no applications in the “Medium” or “High” category, the number of applications the authors found presented a security risk was both surprising and far too numerous. There are over 500,000 applications on the iOS App Store, so extrapolating the results, there could be at least 15,500 applications in the “Low” risk category and 11,500 applications in the “Medium” and “High” risk category.

Overall, the number of applications with some sort of security risk is low. This is not very surprising to the authors as many of these applications are in the “Top” applications list and any potential security flaws would have already been found.

Due to the fact that iOS does not have a robust privilege system, there is no way that a user could know their information was being used in a dangerous or insecure way. While there is support for showing users there is network traffic by using a spinning “network activity indicator”, it is certainly not mandatory for them to do so. In fact, a legitimate or malware application could access the network interfaces, sending and receiving information and never alert the user on iOS.

Developers typically do not follow the principle of least privilege. If an application needs a set of privileges for functionality, they will request them up front, not just when they are needed. This is particularly dangerous because this could be an entry point for an attacker to compromise the application.

[19] performed research where they surveyed 940 Android applications and found that more than 50% required 1 extra unnecessary permission and 6% required more than 4 unnecessary permissions. The reasons that developers may request more permissions than are necessary could be because 1) they don’t understand the importance of security and least privilege, 2) they are planning on future releases that will require these privileges and 3) they don’t fully understand how to work with the platform and make the code function correctly.

Since mobile devices and smartphones are unique in that they have a built-in billing system, there must be ongoing education of developers with emphasis on security and privacy or additional built-in measures in the OS to enforce security over code the developers write or the permissions for which they ask.

6. Using Mobile Devices as Network Monitors

We also researched the possibility of using WiFi sniffing and cracking utilities on the iPhone, as well as the feasibility of releasing a spyware application into the iTunes App Store and collecting user information. As a side note, all the techniques used here could easily be ported to other mobile platforms, such as Android, but this particular research focused on iOS devices.

To be able to perform basic packet sniffing, there are several critical elements that must be performed. The first element is to be able to put the particular interface into a “promiscuous” mode, in the case of wired network interfaces or “monitor” mode, in the case of wireless network interfaces.

In normal network interface operation, the kernel will discard any packets that are not destined to the specific node. Using this “monitor” mode, we are able to capture and further analyze these packets that would normally be discarded. This was a particularly easy piece of code (see Appendix B) to write (if one understands the BSD subsystem and C). In our particular implementation, we have a utility function to toggle the “promiscuous” or “monitor” bit (IFF_PROMISC) in the command word flag (SIOCGIFFLAGS) as well as a function to list all the interfaces that the OS knows about.

In addition to being able to manipulate the firmware of the network card, we also need to be able to access the bpf files or Berkely Packet Filter devices that are located in /dev. These bpf devices “provide a raw interface to data link layers in a protocol independent fashion. All packets, even those destined for other hosts, are accessible through this mechanism [29].”

The access to these files are restricted to root only. This presents a problem for as root access is restricted for applications that will be available in the App Store. Therefore, to install and distribute this application, one must have a jailbroken iOS device.

To give the programmer a more friendly access to the raw data from the bpf device and the packets, a user space program, libpcap (Unix or Linux) or WinPCap (Windows), is bolted onto these kernel-only devices. Interestingly, the authors discovered that the SDK for Mac OS included a pre-built library, libpcap.dylib. Unfortunately, that library is not available natively for iOS, but it can be cross-compiled for the arm architecture by downloading the source from www.tcpdump.org.

Lastly, to perform useful functions with this data, one must create an interface to analyze, extract and filter packet information at the application level. While, a .pcap file could be created for later analysis, it might not be as useful as having live analysis. This can easily be done with a user space program such as tcpdump or WireShark.

This particular research shows there could be a major potential data confidentiality problem with mobile devices. Assuming that the device is jailbroken and if we were able to release an app into the Cydia App Store that a user could download, we could silently harvest and store personal and sensitive information from that particular user, in addition to any other device that is on an open wireless network (assuming that the user was connected), without alerting the user. In addition the being able to sniff packets, since we are in the Cydia App Store, we would have full use of all APIs, including Apple private APIs to harvest personal information.

One question that the authors would like to explore in future research is if we could also use the aircrack-ng suite on mobile devices.

7. Conclusion

In this paper, we examined the history of mobile threats and vulnerabilities as well as current threats and vulnerabilities against mobile devices. We also researched and examined defense mechanisms that currently exist and proposed future research topics. Additionally, we performed two experiments, one as an audit of mobile application security and the other as the feasibility of turning a mobile device into a RF sniffing and data collection device.

Appendix A: Full Application List

Bold applications represent applications bundled with iOS from Apple.

Application

Version

Application

Version

Messages 5.0.1 RedLaser Classic 2.9.8
Calendar 5.0.1 eBay 2.4.0
App Store 5.0.1 Craigslist 3.033
Settings 5.0.1 Key Ring 5.4
Spotify 0.4.21 Coupious 1.4.1
Contacts 5.0.1 Cars 1.6.1
Notes 5.0.1 Amazon PriceCheck 1.2.1
Newstand 5.0.1 Linode 1.0.6
Reminders 5.0.1 Unfuddle 1.1.1
Find My Friends 1.0 MiniBooks 1.0.2
Videos 5.0.1 iTC Mobile 2.4
Vlingo 2.1.1 Blueprint viewer 1.7
Photos 5.0.1 Square 2.2
Camera 5.0.1 WordPress 2.9.2
Instagram 2.0.5 Maps 5.0.1
iMovie 1.2.2 FlightTrack 4.2.2
DashOfColor 3.1 Kayak 19.0.6
ColorSplash 1.7.2 Southwest 1.8.2
UStream Broadcaster 2.1 American 1.3.3
TiltShiftGen 2.02 Fly Delta 1.6
Gorillacam 1.2.2 Flysmart 2.5.25
CameraPlus 2.4 Priceline Negotiator 5.6
PS Express 2.03 Free WiFi 1.1.2
Dropcam 1.4.3 Google Earth 3.2
Chase 2.14.5799 Translator 3.1
Citibank 3.7 Phone 5.0.1
Discover 2.1 Mail 5.0.1
Fidelity 1.6.1 Safari 5.0.1
TD Trader 115.12 Music 5.0.1
PayPal 3.6 Flixster 5.02
Mint.com 2.0 Boxee 1.2.1
Stock 5.0.1 redbox 2.3.1
thinkorswim 115.12 Youtube 5.0.1
Geico 2.0.2 Fandango 4.5
Dropbox 1.4.6 XFINITY TV 1.8
1Password 3.6.1 IMDb 2.3.1
Alarm Clock 1.1 i.TV 3.4.1
Planets 3.1 MobiTV 1.0
Dictation 1.1 Netflix 1.4
Inrix Traffic 3.5.1 VNC 3.2.1
Adobe Ideas 1.2 RDP 2.8
IP-Relay 1.2 TouchTerm 2.1
iLlumination 1.0.1 Scorekeeper 4.1
Fake-a-call 5.05 Statware 1.0.3
HeyTell 2.3.2 NIKE+ GPS 3.2.1
Weather 5.0.1 MiLB Triple A 1.1.0
The Weather Channel 2.1.1 Pandora 3.1.16
Calculator 5.0.1 Shazam 4.8.4
Clock 5.0.1 Soundhound 4.1.1
Compass 5.0.1 iHeartRadio 4.0.1
Voice Memos 5.0.1 Last.fm 3.2.0
AroundMe 5.1.0 Songify 1.0.6
myAT&T 2.1.2 iTunes 5.0.1
WeddingWire 3.1 Virtuoso 1.0
LogTen 3.3.1 I Am T-Pain 2.0.0
French 1.0 Scrabble 1.13.78
Binary Calc 1.4 Harbor Master 2.1
Amazon 1.8.0 Zombie Duck 4.1
Groupon 1.5.7 Zombieville 1.7
LivingSocial 3.2.2 Table Tennis 4.1.0
Yowza 2.5 iFighter 1.9
Coupons Hired Gun 1.8
Airport Utility 1.0 Lock n’ Roll 3.0
Walgreens 3.0.2 Sneezies Lite 1.3
MyHumana 3.0.2 Pad Racer 1.1
Nike + iPod Uno 2.0.0
Gold’s Gym Spotter 1.2 CamWow 2.2
Lose It! 3.7.2 Labelbox 1.3.1
FitnessTrack 1.5.5 Photosynth 1.1.2
LIVESTRONG 1.0.1 Color Effects 3.1
MyFitnessPal Saturation 1.0
Nutrisystem 2.3 Peppermint 1.1
Kindle 2.8.5 FlickStackrXP 1.9.6
Instapaper 4.0.1 Minus 2.1.3
iBooks 5.0.1 Gallery 2.0.1
Zinio 2.2 Handmade 1.1
Twitter 4.0 StubHub 2.4.1
Facebook 4.0.3 Pushpins 2.0.1
Google+ 1.0.7.2940 Black Friday 2.0
foursquare 4.1.2 Sam’s Club 2.1.1
LinkedIn 4.2 Cyber Monday 2.1.0
Meebo 1.95 Words With Friends 4.1
Yelp 5.5.0 Ultimate Free Word Finder 1.01
PingChat Mad Gab 2.0
Bump 2.5.6 Metal Storm 4.0.2
Color 1.1 Need For Speed 1.0.11
Cloudette 1.0.1 Madden NFL 2010
soundtracking 2.0.2 Shizzlr 3.2.1
Free RSS 3.4 Flashlight 5.1
NetNewsWire 2.0.5 Tip Calculator 1.3.1
FOX News 1.2.4 PCalc Lite 2.4.3
OpenTable 3.4.2 Fake Call 1.1
Urbanspoon 1.17 To Do 3.2
Epicurious 3.0.1 Google 1.0.0.8117
WinePhD 1.2 Evernote 4.1.6
TabbedOut 2.3.3 Coin Flip 2.2
Foodspotting 2.7 Grades 2 2.03
GrubHub 2.20 Sundry Notes 3.2
RecipeGrazer 1.3 OneNote 1.2
Starbucks 2.1.1 Enigmo 4.1
Starbucks Mobile Card Angry Birds 1.6.3
Ness 1.1 JellyCar 1.5.4
iDisk 1.2.1 Runway 1.6
Remote 2.2 RockBand Free 1.3.49
Apple Store 2.0 Game Center 5.0.1
Find iPhone 1.3 App For Cats 1.1
Pages 1.5 PadRacer 1.1
Places 1.31 Implode 2.2.4
TripAdvisor 5.9 Astronut 1.0.1
Google Latitude 2.2.1 Monopoly 1.2.9
Gas Buddy 1.10 Deliveries 4.5
Maplets 2.2.2 Skype 3.5.454
iTranslate 5.1 Units 2.1.2
Translate 1.6.2 NCAA Football 2011
KG Free ESPN ScoreCenter 2.2.2
Wikipedia 2.2 Ski Report 2.2.1
White Noise 5.0.3 EpicMix 2.0.1
Sleep Machine Lite 2.0.1 MLB At Bat 4.6.1
Inception 1.6 Purdue 3.0
Sleep 2.0.1 NASA 1.43
Night Stand 1.0.4 80,000 Wallpapers 1.98
Geico BroStache 1.0.1 Wedding 911 1.06
CamCard 2.6.0.4 Path 2.0.2
Offline Pages 1.5.2 Facebook Messenger 1.5.2
GPS Tracker 1.2.2 Quora 1.1
TextPics Free 2.2 Big Button Box 3.0
Peel 2.0

Appendix B

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
int go_promisc(int);
int get_iface_list(struct ifconf *);
int get_iface_names(void);
int go_promisc(int on) {
int fd;
struct ifreq *ifreq = (struct ifreq *)malloc(sizeof(struct ifreq));
get_iface_names();
strcpy(ifreq->ifr_name, "en0");
fd = socket(AF_INET, SOCK_STREAM, 0);
if(fd < 0) {
perror("opening socket");
return -1;
}
int status = ioctl(fd, SIOCGIFFLAGS, ifreq);
if(status < 0) {
perror("ioctl(SIOCGIFFLAGS)");
status = -1;
}
if(on) {
ifreq->ifr_flags |= IFF_PROMISC;
ifreq->ifr_flags |= IFF_ALLMULTI;
}
else {
ifreq->ifr_flags &= ~IFF_PROMISC;
ifreq->ifr_flags &= ~IFF_ALLMULTI;
}
status = ioctl(fd, SIOCSIFFLAGS, ifreq);
if(status < 0) {
perror("ioctl(SIOCSIFFLAGS)");
status = -1;
}
close(fd);
return status;
}
int get_iface_list(struct ifconf *ifconf) {
int sock, rval;
sock = socket(AF_INET, SOCK_STREAM, 0);
if(sock < 0) {
perror("opening socket");
return (-1);
}
if((rval = ioctl(sock, SIOCGIFCONF, (char *)ifconf)) < 0) {
perror("ioctl(SIOGIFCONF)");
}
close(sock);
return rval;
}
int get_iface_names() {
static struct ifreq ifreqs[20];
struct ifconf ifconf;
int  nifaces, i;
memset(&ifconf, 0, sizeof(ifconf));
ifconf.ifc_buf = (char*) (ifreqs);
ifconf.ifc_len = sizeof(ifreqs);
if(get_iface_list(&ifconf) < 0) {
return -1;
}
nifaces =  ifconf.ifc_len / sizeof(struct ifreq);
printf("Interfaces (count = %d)\n", nifaces);
for(i = 0; i < nifaces; i++) {
printf("\t%-10s\n", ifreqs[i].ifr_name);
}
}
int main(int argc, char *argv[]) {
if(argc != 2) {
printf("usage: promisc [ON | OFF]");
return -1;
}
get_iface_names();
if(strcmp(argv[1], "ON") == 0) {
return go_promisc(1);
}
else if(strcmp(argv[1], "OFF") == 0) {
return go_promisc(0);
}
else {
printf("usage: promisc [ON | OFF]");
return -1;
}
return 0;
}

References

[1] M. Hypponen, “Malware Goes Mobile”, November 2006, Scientific American Magazine. Pages 70–77. http://www.cs.virginia.edu/~robins/Malware_Goes_Mobile.pdf

[2] J. Bickford, O. O'Hare, A. Baliga, V. Ganapathy, and Iftode. L, “Rootkits on Smartphones: Attacks, Implications and Opportunities”. ACM, In the Workshop on Mobile Computing Systems and Applications. Annapolis, MD. Feb. 2010.

[3] N. Seriot, “iPhone Privacy”, Black Hat DC 2010. Arlington, Virginia, USA. http://seriot.ch

[4] R. Schlegel, K. Zhang, X. Zhou, M. Intwala, A. Kapadia, X. Wang, "Soundminer: A Stealthy and Context-Aware Sound Trojan for Smartphones”. In Proceedings of the 18th Annual Network & Distributed System Security Symposium (NDSS) Feb. 2011.

[5] J. Rocha. “The Droid: Is this the smartphone consumers are looking for?”. Nov. 2011. http://blog.nielsen.com/nielsenwire/consumer/the-droid-is-this-the-smartphone-consumers-are-looking-for/

[6] A. Bose. “Propagation, detection and containment of mobile malware”. 2008. http:/hd1.handle.net/2027.42/60849

[7] http://www.symbianpoint.com/types-latest-list-mobile-viruses.html

[8] A. Gostev. “Mobile Malware Evolution: An Overview, Part 1”. Sep. 2006. http://www.securelist.com/en/analysis?pubid=200119916

[9] McAfee. “McAfee Threats Report, Third Quarter 2011”. 2011. www.mcafee.com/us/resources/reports/rp-quarterly-threat-q3-2011.pdf

[10] A. Felt, M. Finifter, E. Chin, S. Hanna, D. Wagner. “A Survey of Mobile Malware in the Wild.” ACM CCS Workshop on Security and Privacy in Smartphones and Mobile Devices (SPSM). Oct. 2011.

[11] T. Martin, M. Hsiao, D. Ha, J. Krishnawami. “Denial-of-Service Attacks on Battery Powered Mobile Computeres”. Proc. of Second IEEE Annual Conference on Pervasive Computing and Communications (PERCOM). 2004.

[12] K. Aras. “Jailbreaking iOS - How an iPhone breaks free.” Stuttgart Media University.

[13] Google. “Application Signing”. 2011. http://developer.android.com/guide/publishing/app-signing.html

[14] Apple. “Configuring Development Assets”. 2011. http://developer.apple.com/library/IOs/#documentation/Xcode/Conceptual/ios_development_workflow/100-Configuring_Your_Developmet_Assets/identities_and_devices.html

[15] “Code Signing.” 2011. http://en.wikipedia.org/wiki/Code_signing

[16] The iPhone Wiki. 2011. http://www.theiphonewiki.com/wiki/index.php

[17] S. Loueiro, R. Molva, Y. Roudier. “Mobile Code Security”. Institut Eurecom. 2011. http://www.eurecom.fr/~nsteam/Papers/mcs5.pdf

[18] C. Miller, “Mobile Attacks and Defenses”, IEEE Security and Privacy. Vol. 9, Issue 4, Pages 68-70, July-Aug 2011

[19] A. Felt, E. Chin, S. Hanna, D. Song, D. Wagner. “Android Permissions Demystified”. Proceedings of ACM conference on COmputer and Communications Security (CCS 2011). 2011.

[20] W. Enck, D. Octeau, P. McDaniel, S. Chaudhuri. “A Study of Android Application Security.” Proceedings of the 20th USENIX Security Symposium. 2011.

[21] H Shacham, M. Page, B. Pfaff, E. Goh, N. Modadugu, D. Boneh, “On the effectiveness of address-space randomization”. Proceedings of the ACM conference on Computer and Communications Security (CCS’04). New York. 2004.

[22] R. Hund, T. Holz, F. Freiling. “Return-oriented rootkits: bypassing kernel code integrity protection mechanisms”. Proceedings of ACM 18th Conference on USENIX Security Symposium (SSYM’09). Berkeley, CA. 2009.

[23] T. Blasing, L. Batyuk, A.D. Schmidt, S. A. Camtepe. S. Albayrak. “An Android Application Sandbox System for Suspicious Software Detection.”

[24] A. Shabtai. “Malware Detection on Mobile Devices”. Proceedings of IEEE on Mobile Data Management. Pages 289-290. 2010.

[25] S. Dai, Y. Liu, T. Wang, T. Wei, W. Zou. “Behavior based malware detection on mobile phones”. IEEE Wireless Communications Networking and Mobile Computing (WiCOM). Pages 1-4. 2010.

[26] G. Zyba, G. Voelker, M. Liljenstam, A. Mehes, P. Johansson. “Defending mobile phones from proximity malware”. Proceedings of IEEE INFOCOM. 2009.

[27] H.S Chiang, W.J. Tsaur. “Identifying smartphone malware using data-mining technology”. Proceedings of IEEE Computer Communications and Networks (ICCCN). Pages 1-6. 2011.

[28] O. Mencer, M. Mar, M.J. Flynn. “Hardware Software Tri-Design of Encryption for Mobile Communications Units.” Proceedings of IEEE Acoustics, Speech and Signal Processing. 1998.

Recently I started doing some interesting security work. I downloaded a great series from Vivek Ramachandran on 802.11 Wireless Hacking. For the series, he suggested using the Alfa Networks AWUS036h card. Because I have a wedding coming up and I need to save money, I wanted to see if I could get it working without that since I had an old USB dongle from NetGear (WG111v1). When I plugged it in initially to my BT5 VM, it brought up the error message “(p54usb) cannot load firmware isl3887usb (-2)”. Using ndiswrapper is a fine way to go if you never plan on using monitor mode with the network card but for the tutorial series, I needed to have this capability. To solve this issue, simply use the following command and you’ll be good to go with your wireless adapter if it can use the p54 driver.
apt-get install linux-firmware-nonfree

This was all discovered after several hours of building drivers, realizing that I accidentally downloaded the x64 version of BT5 (which is why the drivers weren’t working), ndiswrapper doesn’t (and won’t ever) support monitor mode.

Abstract— With the Internet becoming a major resource for many individuals, business, universities and countries, there is an increasing amount of traffic on the Internet.  Some applications available on the Internet need to be able to provide stringent performance guarantees from their web servers (such as online securities trading).  Due to the fact that Internet traffic is bursty and unpredictable, and the interactions between hardware and software in multi-tier systems are complex, there needs to be a large degree of atomicity to capacity planning.

Index Terms—capacity planning, multi-tier systems, requests, sessions, performance, autonomic computing, distributed systems

I. Introduction

The Internet has become an important and popular channel for a variety of different services, such as news aggregation, online shopping, social networking or financial brokerage and other services. Many of these popular services on the Internet today, such as Facebook, Twitter, Amazon and eBay [2, 5, 9] are composed of a generic multi-tier architecture.  Requests generated by users flow through each layer in this architecture.  Each tier in this system provides certain functionality to the following tier by executing part of the incoming request [5].  This multi-tier system includes 1) a web tier running a web server to respond to incoming requests, such as Apache 2) an application tier that is running an application container which hosts an application, such as Tomcat 3) and a backend database tier running database software such as MySQL.

Tiered Application [2]

Each of these tiers may be a single machine or may be distributed over a cluster of nodes.  In addition, these servers may be virtualized, such that multiple applications can be hosted and run on the same physical node.  Often times, to ensure acceptable performance, especially in application hosting, there are service level agreements (SLA) that are put into place to govern the desired system performance.  An SLA can specify one or multiple parameters, such as required total uptime of a system, total throughput, average end-to-end delay of requests within a certain percentile, etc.  The SLA target is maintained by the addition of resources into each tier and can be maintained by removing resources as necessary (without violating the SLA).

Traffic on a computer network is inherently non-uniform and hard to predict, mainly due to “think” time of the end user.  This “bursty” behavior is characterized by short, uneven spikes of peak congestion in the life of an application [4].  Popular services can experience dynamic and varying workloads that depend on popularity, time or date, or general demand.  In addition, Internet flash crowds can cause bursty and unpredictable workloads in each of these tiers.  For example, in November 2000 holiday season, Amazon.com experience a forty-minute downtime due to an overload [5].  These flash crowds can cause a significant deviation from the normal traffic profile of an application, affecting the performance.

The performance of the system can be characterized by the total measured end-to-end delay generated by these incoming requests and their workload each tier.  Due to the fact that the interactions between the software and hardware in each of these aforementioned tiers can be quite complex, the management process of allocating sufficient resources (CPU, disk, network bandwidth, etc.) to each tier such that they don’t saturate and become a bottleneck in the system is often a difficult, lengthy and potentially error-prone process to model and estimate for human operators.  For example, if the performance of an application tier dominates the performance of the system, that tier becomes the bottleneck.  It is non-trivial to model the process (scheduling, algorithms, memory, I/O and CPU times) and time it takes to execute the business logic in this tier, especially if resources are shared, as is common in distributed systems.  In addition to these problems, static allocation does not address the issue of Internet flash crowds and the potential they have to overload the system and jeopardize the SLA compliance.

Capacity planning and autonomic resource management plays an important role in modern data centers.  Service differentiation (Quality of Service) and performance isolation help these complex systems to adapt to changing workloads within the system as a whole and within each tier.  In this paper, we will present a survey of the large variety of models, techniques and results of autonomic resource management in large-scale, multi-tier systems.

II. Network Traffic Characteristics

To truly understand the reason for capacity planning and the difficulties it presents in modeling in terms of the interactions between the incoming requests and the hardware and software that service them, we have to understand network traffic characteristics.  Incoming session and request rates tend to fluctuate based on a variety of different factors.  These varying workloads could be characterized as “bursty”, which is defined by [4] as short, uneven spikes of peak congestion during the lifetime for the system.  These traffic patterns deviate significantly from the average traffic arrival rates.

One way to characterize burstiness as seen in [4] is to use the variable I to represent the index of dispersion.  The index of dispersion is used to measure whether a set of observed occurrences are clustered or dispersed compared to a standard model.  When I is larger, the observed occurrences of bursty traffic is more disperse.  We can see that in Figure 1, burstiness can aggregate into different periods represented by different indices of dispersion.

 

Figure 1

A simple way to calculate the index of dispersion for a particular is as follows:

where Nt is the number of requests completed in a time window of t seconds, where t seconds are counted ignoring server idle time, Var(Nt) is the variance of the number of completed requests and E[Nt] is the mean service rate during busy periods.  An astute reader can deduce that as t becomes large, if there are no bursty periods within t, the index of dispersion is low.

Now that bursty periods can be quantified via I, what causes burstiness?  [4] suggests that “burstiness in service times can be a result of a certain workload combination” and “burstiness in service times can be caused by a bottleneck switch between tiers and can be a result of “hidden” resource contention between the transactions of different types and across different tiers.”  That is, one server or tier may be lightly loaded during a particular period, but may become saturated in other periods where a large number of requests are processed.

This hidden resource contention and different types of transactions across different tiers can be extremely difficult to model and even more troublesome for human operators to correctly provision for.  Autonomic provisioning of system resources is needed to optimize service metrics.

III. Self-Management

As previously mentioned, the major motivation behind autonomic resource management and capacity planning is to reduce the human involvement in these activities due to their difficulty.  If the systems are able to plan for the future and react to the present without operator input, it will take the load off of system administrators and more accurately respond to the situation at hand.  In order to do this, one has to define the goals and properties of such an autonomic system.  The main properties of an autonomic system, as cited in [1] are:

  • Self-configuration: autonomic systems configure themselves based on high level goals, specifying what is desired (SLAs), not how to achieve the goals.  Systems with self-configuration can install and set themselves up.
  • Self-optimization: autonomic systems can optimize its use of resources either proactively or reactively in an attempt to improve service and meet SLAs.
  • Self-healing: autonomic systems can detect and diagnose problems at both high and low levels (software and hardware).  Autonomic systems should also attempt to fix the problem.
  • Self-protecting: autonomic systems should protect itself from attacks but also from trusted users trying to make changes.

One particularly important feature of autonomic system is the ability to exhibit “proactive” features.  For example, software or hardware agents should be able to be:

  • Autonomic: Agents operative without direct intervention of humans and have some kind of control over their actions and internal state [1].”
  • Social: “Agents interact with other agents via some agent-communication languages [1].”
  • Reactive and proactive: “Agents are able to perceive their environment and respond in a timely fashion.  Agents do not simply act in response to their environment, but they are able to exhibit goal-directed behavior in taking the initiative [1]

In order to model these properties, IBM suggested a general framework autonomic control loop, MAPE-K as detailed in [1].  MAPE-K allows for clear boundaries in the model to classify the work that is taking place in the autonomic system.  In MAPE-K, there are managed elements, which represents any software or hardware resource that is managed by the autonomic agents.  Sensors collect information about managed elements and provide input to the MAPE-K loop such that the autonomic manager can execute the changes.  Typically the managers are additional software components configured with high-level goals which leaves the implementation of these goals up to the autonomic manager.  Effectors actually carry out the changes to the managed elements (these changes can be fine or course grained).  Each of these elements can be observed in the following sections.

In the MAPE-K loop, there are five different components: monitor, analyze, plan, execute and knowledge.  Monitoring involves “capturing properties of the environment (psychical or virtual) that are important to the self properties of the autonomic system [1].”  This information is captured from sensors in the system in two different ways, passively (using built in tools to run an analysis on the system) or actively (engineering the software to monitor and improve performance).

In the planning model of MAPE-K, the manager uses the monitoring data from the sensors to produce a series of changes to one or more managed elements.  These changes can be calculated by having the autonomic system keep state information about the managed elements and data so that adaptation plans can be adjusted over time.  An additional benefit of keeping state information is that systems are able to create an architectural model where the actual system mirrors the model and proposed changes are able to be verifying that the system integrity is still in tact before and after the proposed changes.  If any violations occur after applying the changes to the model, the changes can be aborted or rolled back to avoid damage or downtime to the system.

In the knowledge part of the model, the knowledge used to effect adaptation can come humans, logs, sensor data, or day-to-day observation of a system to observe its behavior [1].  In this part of the model, there is a large space that one can use machine learning to acquire knowledge about the system.  While [1] suggested reinforcement learning and Bayesian techniques, other authors [2] suggest K-Nearest Neighbors (KNN) and neural networks [7] with fuzzy control.  This author would suggest that decision trees could be an effective method of acquiring the knowledge to effect the proposed plans.  Also, clustering could be used as a way of identifying and classifying previously similar plans to see if they were successful or if they resulted in failure.

Finally, there are several different levels of automaticity including: Basic, Managed, Predictive, Adaptive and Fully Autonomic.

Now that we have seen a general framework for automated resource management, let’s continue to explore each component.

  1. Managed Elements

Managed elements in an autonomic system consist of all the hardware and software elements that can be managed by autonomic agents.  Due to the fact that multi-tier systems can be very complex, there are multiple levels of detail that one can view the system.

The first and highest level is where the system is viewed as a black box.  At this level, we consider the end-to-end delay when the request enters the system and returns back to us.  If there is congestion or delay caused by insufficient capacity at any tier, we are unable to know which tier’s capacity is causing the problem. Typically, changes in allocation to capacity are fairly course-grained at this level.  [8] plans their allocation strategy at this level.

At the next level down, we no longer monitor system performance by a single delay metric.  We are now able to monitor the performance of individual tiers.  When congestion occurs at a single tier, we are able to target that tier and increase the allocation capacity of just that tier.  However, one must be careful not to trigger downstream allocations with the increased capacity at the original tier.  [5] plans their allocation strategy at this level.

Lastly, at the most fine-grained level, we are able to collect statistics on individual components within a tier such as CPU usage for an application on a particular node.  Figure 2 shows an example of the black-box and per-tier paradigms.

 

  1. Autonomic Managers and Controllers

In the MAPE-K loop, the monitoring, analyzing and planning phases are done in the control plane or autonomic manager.  The manager should adjust managed elements in the following fashion: [2]

  • Prompt. It should sense impending SLA violations accurately and quickly and trigger resource allocation requests as soon as possible to deal with load increases (or decreases).
  • Stable. It should avoid unnecessary oscillations in provisioning resources (adding and removing).

Keeping the two guidelines in mind, there are two important decisions that every autonomic manager will be making: 1) when to provision resources and 2) when a provisioning decision is made, how much of a particular resource should be provisioned.

When To Provision

When considering the question of “when to provision”, one must consider the timescale that is being evaluated.  There are two main methods of provisioning: predictively and reactively.  Predictive provisioning attempts to stay ahead of the workload, while reactive provisioning follows to correct for short term fluctuations.

In predictive provisioning, the autonomic system is planning increased (or decreased) capacity for the future.  When evaluating real-world workloads, typically the system or application will see a peak in traffic during the middle of the day and be the minimum during the middle of the night [5].  Other factors, such as recent news (breaking important stories) or seasons (holiday shopping) can affect this distribution of traffic.  By using predictive analysis, automated systems are able to provision sufficient capacity well in advance of any potential events that would cause SLA violations.

Prediction can be done via a number of different methods including statistical analysis, machine learning, or by simply using past observations of workload.  This prediction is usually implemented in the control plane or autonomic manager of the system [2, 5, 6, 7, 8].  For example in [2], a scheduler for each application monitors the application database tier and collects various metrics, such as average query throughput, average number of connections, read/write ratios and system statistics such as CPU, memory and I/O usage, about the system and application performance.  These metrics are reported back to the autonomic manager and an adaptive filter predicts the future load based on the current measured load information.  Each of these metrics are weighted to reflect the usefulness of that feature.  In addition, a KNN classifier determines if an SLA is broken and redirects the source allocation to adjust the number of databases such that that tier is no longer in violation.  A resource allocation component decides how to map the resources dynamically.  [7] uses self-adaptive neural fuzzy controller to decide upon the allocation of resources.  Moreover, [6] uses a model estimator which automatically learns online a model for the relationship between an application’s resource allocation and it’s performance and a optimizer which predicts the resource allocation required to meet performance targets.  Lastly in [5], the authors use a histogram of request arrival rates for each hour over several days.  Using that data, the peak workload is estimated as a high percentile of the arrival rate distribution for that hour.  By using these metrics, the application is able to predict shifting workloads in a sliding window.

Most of the papers survived use the error in prediction e(k) (that is, the predicted workload or arrival rate λpred(t) and the observed workload or arrival rate λobs(t) for a time period t) or the change in error in prediction Δe(k) (e(k) −e(k −1)) as input to their algorithms to help determine the next periods allocation [5, 6, 7].  Since workloads and arrival rates often exhibit bursty overloads [4, 5], these parameters fine-tune our prediction model.

Proactive provisioning alone is not enough to make the system robust and immune to SLA violations.  For example, there may be errors in prediction if workload or arrival rate deviates greatly from previous days.  As mentioned earlier, Internet flash crowds can spike network requests have the potential to cause congestion and overload the system due to their bursty, unpredictable nature.  In these cases, the errors would lag behind the actual events and there would be insufficient capacity.

Reactive provisioning can be used to quickly correct any deviations from these unpredicted events.  Reactive provisioning is used to plan on a shorter time scale, perhaps on several-minute basis.  If anomalies are detected, reactive provisioning can quickly allocate additional capacity to the affected tiers so they don’t become a bottleneck.

In [5], the authors implement reactive provisioning by comparing the predicted session arrival rate λpred(t) and the observed arrival rate λobs(t) for a time period t.  If these two measurements differ by more than a threshold, they take corrective provisioning action.  In [2], the resource manager monitors the average latency receiver from each workload scheduler during each sampling period.  The resource manager uses a smoothened latency average computed as an exponentially weighted mean of the form WL = α ×L + (1 –α) ×WL, where L is the current query latency.  When the α parameter is larger, the system is more responsive the average to current latency.  In [6], the authors attempt to reactively provision limited resources by using an auto-regressive –moving-average (ARMA) model, where two parameters a1(k) and a2(k) capture the correlation between the applications past and present performance and b0(k)  and b1(k)  are vectors of coefficients capturing the correlation between the current performance and the recent resource allocations.  Note that if the spike in traffic is large, it may require several rounds of reactive provisioning to get the capacity to an acceptable level.

In [8], the authors consider provisioning resources based on “what-if” analysis.  They argue that most of web applications consist of services that form an acyclic directed graph, which can be formed into a decision tree.  In their model, they ask each tier to predict, online, future performance in the event it received an additional capacity unit or had one capacity unit removed.  The performance model in [8] uses the following equation to calculate response time:

where, Rserver is the average response time of the service, n is the number of CPU cores assigned to the service, λ is the average request rate and Sserver is the mean service time of the server.  When a threshold of service time is exceeded, re-computation of service time occurs.  These predictions are given to the parent node.  Using these predictions, provisioning agents negotiate resources with each other based on maximum performance gain and minimum performance loss.  The root node selects which services to provision across the tree when the SLA is about to violated, or de-provision, if resources can be removed without causing an SLA violation. Furthermore, in [8], the authors also consider how provisioning cache instances using the previously described “performance promises” would affect workloads in a particular tier and all children tiers due to an increased hit rate.  Figure 3 from [8] illustrates the decision process:

Figure 3

We can see that service I has k immediate children services and it aggregates it’s own performance promises as follows:

Lastly, while the majority of the papers reviewed were concerned with provisioning additional capacity, [2] also considered removing unneeded capacity.  If the average latency is below a low-end threshold, the resource manager triggers a resource removal.  The system then performs a temporary removal of the resource.  If the average latency remains below the low threshold, the resource is permanently removed.  The reason that a temporary removal is performed first is that mistakenly removing a resource is potentially a costly operation if it negatively impacts the system performance.  The main motivation behind this logic is that unused resources are wasted if they are being under-utilized in the system.

When comparing the effectiveness of reactive and proactive, Figure 4 from [5] that proper proactive provisioning can greatly reduce the time spent in violation of the SLA.

Figure 4

In addition to handling smoothly increasing workloads, the provisioning techniques from [5], as shown in Figure 5, predictive provisioning can also handle sudden load bursts effectively.

Figure 5

By combining predictive and reactive provisioning, systems are able have sufficient capacity to handle predictable workloads as well as short-term instabilities.

How Much To Provision

The question of “how much of a given resource to provision” is less straightforward than “when to provision.”  As we stated earlier, it may be necessary to go through several rounds of provisioning before the end-to-end delay is at an acceptable level.  Moreover, depending on the implementation and type of controller you use, the model determining “how much” could be different.  However, all provisioning algorithms attempt to provision enough to meet the SLA, within a time period t, without overprovisioning, because that would be a waste of resources.  Additionally, one critical factor to consider and try to avoid is that increasing the provisioning at a particular tier k might create a downstream bottleneck at tier k + n, assuming n tiers.  Several authors in the survey explore how to avoid this phenomenon.

The authors in [5] present a general framework for determining provisioning needs based on average end-to-end latency.  Suppose a system that has n tiers, denoted by T1, T2,…TN and let R denote the desired end-to-end delay.  Suppose further that the end-to-end response times are broken down into per-tier response times denoted by d1, d2,…dN, such that Σ di = R.  Lastly, assume that the incoming session rate is λ.  Typically, one would want to provision the system for the worst-case scenario, that is the peak of λ.  Individual server capacity can be modeled using M/M/1 first come, first serve (FCFS), non-preemptive queues and each request in the queue has a certain amount of work to do.

Assuming the service rate of the queue is μ, then λ ⁄ μ = ρ, would be the service ratio.  If ρ is less than 1, then the queuing delay, that is, the amount the request waits in the queue to be serviced is bounded and finite.  If ρ is equal to 1, the queue length is infinite but queuing delay is only infinite if the inter-arrival times of requests are not deterministic.  Lastly, if ρ is greater than 1, then the queuing delay is infinite.  This can express useful data, such as service time (the queuing delay and the time it takes to execute the request).  This behavior can be modeled in the queuing theory result [9]:

where di is the average response time for tier i, si is the average service time for a request at that tier and λi is the request arrival rate at tier i.  is the variance of inter-arrival time and the variance of service time, respectively, which can be monitored online.  Using this equation, we can obtain a lower bound on a request rate for server i.  Assuming a think-time of Ζ, then request are issued are a rate of (1 / Ζ) [5].  Therefore, the number of servers ηi needed at tier i to service a peak request rate can be computed as:

where βi is a tier specific constant, τ is average session duration, λi is the capacity of a single server and λ is the request arrival rate.  The authors in [5] assume that the servers in each tier are load balanced, although other models do exist that explore provisioning without load balancing, such as [10].

In [7], the authors use a neural fuzzy controller with four layers to determine how much of a particular resource should be (re) allocated.  In their controller design, they have a neural controller with four layers (see Figure 6).

Figure 6

In layer 1, the input variables e(k) and Δe(k) are passed into the neural controller nodes.  In layer 2, each node in this layer acts as a “linguistic term” assigned to one of the input variables in layer 1, where they use their membership functions to determine the degree to which an input value belongs to a fuzzy set (i.e. negative large corresponds to the numeric value -50).  Layer 3 uses the outputs from layer 2 multiplied together to determine the firing strength of a particular rule in layer 3.  Lastly, in layer 4, the output of layer 3 is “defuzzified” into numeric output in terms of resource adjustment Δm(k).  The magnitude of adjustment is determined by the online learning of the neural fuzzy controller, described in more detail in [7].  This online learning algorithm is able to adapt quite rapidly to stationary and dynamic workloads to guarantee 95th-percentile delay, as seen in in Figure 7 from [7].

Figure 7

In [6], the authors use the optimizer to determine changes in resource allocations for finite resources such as disk and CPU.  This is a significant departure from other models in that it is assumed that we have a (much) larger pool of resources (essentially unlimited) to allocate increased resources from.  Their optimizer uses uar as the resource allocation required to meet the performance target or SLA.  The optimizer’s high-level goal is to determine an allocation in a stable manner (no resource oscillations) by using a cost minimization function to find the optimum resource assignments.  In their cost minimization function:

where Jp = (yna(k) – 1)2 serves as a penalty for deviation of the application performance from the desired target and Jp = ||ura(k) – ua(k – 1)||2 serves as a control cost function to improve stability of the system.  The controller will attempt to minimize the linear combination of both functions.  One important point to note in this particular allocation scheme is that allocation requests are confined by the following constraint:

where urirt is a tuple of requested resources for application i, resource r for tier t.  Stated another way, the allocations for all applications for a particular resource, such as CPU or disk, in a particular tier must be less than or equal to100%.  When this constraint is violated, a particular resource is experiencing contention.  It is important to note that in this allocation scheme, while there exists the potential for all application to receive adequate capacity to satisfy demand, when contention exists, applications are weighted according to their priorities in the minimization function so that most “important” application receives the largest share of the divided resources.  Clearly, because we cannot allocate more than 100% of a node’s physical CPU, disk or other resource, all applications suffer from performance degradation – the only difference is to what extent the application suffers that degradation.

Other authors of course decide how much to provision based on their controller implementation.  In [2], the authors use a k-nearest neighbors classifier to decide the number of databases to be provisioned.  Lastly, in [8], use a decision tree process to determine the maximum performance gain (and minimal performance loss) to allocate or remove additional resources.  The performance of the algorithm in [8] was quite impressive in observing it’s SLA and remaining well-provisioned without wasting resources as see in Figure 8.

Figure 8

Before looking at additional MAPE-K components, it is worth looking at solving two additional enhancements to resource provisioning: preventing downstream bottlenecks and preventing allocation oscillations.

  1. A. Preventing Downstream Bottlenecks

The relationship between an incoming request and the work units at successive tiers are not necessarily 1-to-1.  A single incoming search request at the web tier may trigger more 1 more query requests at a database tier.  Therefore, downstream tier capacity has to be considered when allocating additional capacity at upstream tiers.

First, consider what would happen if additional downstream tiers were adjusted for additional incoming requests.  When an increase in allocation is triggered by an SLA violation at tier k, the capacity will increase by n.  If the downstream tier k + 1 is almost to capacity, that tier now has an additional n requests to service, which has the potential to cause an SLA violation.  When the resource manager detects a potential violation at tier k + 1, there will be another round of provisioning.  In the meantime, due to the fact that it takes a fixed amount of time to provision additional resources, tier k + 1, could be in violation.  Following a pattern, this could cause up to k provisioning events.  Clearly, this cascading chain of allocation, violation and additional provisioning, which in addition to being wasteful, increases the total time in violation of the SLA.  [5] proposes a solution by using the constant β, where if βi is greater than one if the request triggers multiple requests at tier i or less than one if caching at prior tiers reduces the work at this tier.

  1. B. Preventing Allocation Oscillations

Due to the fact that internet traffic has a bursty nature, there is a potential for a rapidly fluctuating load in the system.  Because of this fact, a necessary enhancement to the system controller should be a filter to smooth or dampen very brief load spikes.  This is not to say that we don’t want to respond to all SLA violations, but adding or removing additional capacity can potentially be a very costly and time consuming operation.

In addition, in [2], the authors keep state on the additional allocation, as either STEADY or MIGRATION state.  During the MIGRATION state, it may take a period of time after the SLA violation and associated additional capacity allocation is triggered for the migration of additional resources to occur and “warm-up.”  [2] found that latency may continued to be high or even increase during this period, and as such, sampling during this period may not be reflective of the actual system state.  Furthermore, they found that making decision based on samples from this migration and warm-up time period, may continue to add unnecessary replicas which will need to be removed later.  This is wasteful and could penalize other applications hosted on the same machine.

For additional information on each model and provisioning algorithm, refer to the related paper.

  1. Effectors

The execution of the plan in the MAPE-K loop happens with the effectors. In some of the papers that were surveyed, [citation needed – 5?], the authors used request policing to ensure that the admission rate does not exceed the capacity.  Any extra sessions beyond capacity are dropped at the threshold of the system.  Once the request was admitted, it was not dropped at any intermediate tier.  Conversely, each tier could have their own request policing mechanism however, this is quite wasteful as requests that have had prior work done, may be dropped at downstream tiers.

In the majority of the papers [2, 5, 6, 7, 8], additional capacity was allocated from some pool of free resources.  If no more free resources existed or that resource reached it replication maximum, resources were re-provisioned or the sessions and requests were capped at a maximum. In [2], additional database capacity was added to the tier by replicating the existing database.  During the period of migration, requests were held and then when the migration was complete, they were “played” in stages to bring the new copy up to date with the current copy with any additional writes that may have occurred during migration.

In [5], the authors used agile server switching.  In this model, each node had a copy of the application running in a separate virtual machine (VM) however, only one application was active at a time.  When the control plane determined that it needed to allocate additional capacity, if the application running on a particular node schedule for replacement was not the application receiving the additional capacity, the sessions and request were ramped down using fixed-rate or measurement-based techniques.  Once all the sessions had been concluded for the previous application in that VM, it was suspended and the new allocation was brought up.  This allowed new applications to quickly be provisioned for additional capacity.

However, admission control may not be the best choice and [3] presented an alternative to dropping sessions by allocating additional capacity in a “degraded mode.”  Using traditional control theory (having a closed loop that reacts to sensors and actuators), we can readily adjust the load on the server to stay within bounds of process schedulability based on available resources.

The actuator or effector is responsible for performing a specific action based on controller output.  In the case of [3], they initially used admission control as a way of controlling server load.  This limits the number of clients that the server can respond to concurrently.  All other clients are rejected and while this is not a favorable outcome, it is a way of providing QoS to other clients.

However, this actuator can be adapted to provide a “degraded” level of service.  In this “degraded” level of service, the content that is served to the client receiving the degraded service is different than that which the “full service” client receives.  For example, the degraded content may have less content such as images in it.  To perform this degradation, there must be multiple versions of the content and the web server will serve the content from the appropriate file structure at request time.  There can be m different service levels where m = I + F (I is the service level where F is the fraction of clients who are served at level I).  When m = M, all clients receive the highest service and conversely when m = 0, all clients are rejected.  This allows a more general model of saying that a percentage of clients will receive degraded service, rather than specifically specifying which clients (which clients may be addressed through different functionality, such has hashing their IP address).  The server load is control through the input of the variable m.

The monitor proposed in [3] is expressed as the utilization U as a function of served request rate R and delivered byte bandwidth W (U = aR + bW, where a and b and derived constants through linear regression).  This function is able to approximate the maximum utilization rate for deadline-monotonic schedulers to meet deadlines of U < 0.58.  Using this scheme of admission and “capacity” planning, the authors in [3] were able to admit almost 3 times the number of requests to the system as shown in Figure 9 before significant service degradation occurred.

Figure 9

  1. Sensors

Sensors are part of the knowledge phase in the MAPE-K loop.  The sensors that report data to the control plane can be any number of metrics.  In the papers surveyed, there were authors that used CPU usage [5, 6], bandwidth, throughput, active network connections [2, 5], I/O transfer [2, 6], cache hits [8], end-to-end delay or response time [5, 7], session arrival rate [5], request arrival rate [5], read/write ratios [2], lock ratios [2] and memory usage [2].  These parameters can be recorded and monitored online or offline, using standard system tools such as vmstat, iostat and sysstat or custom written software to record statistics.

IV. Quality of Service & Performance Isolation

Lastly, the control theory approach was extended in [3] using virtual servers to show support for performance isolation (each virtual server can guarantee a maximum request rate and maximum throughput), service differentiation (each virtual server supports request prioritization) and excess capacity sharing (conforming virtual servers under overload can temporarily exceed capacity to avoid client degradation).

With performance isolation, a virtual server is configured with a maximum request rate RMAX and a maximum delivered bandwidth of WMAX.  This expresses an throughput agreement to serve up to the specified levels.  If RMAX is exceeded, then the agreement on WMAX is revoked.

In performance isolation, the virtual server can adapt content as previously mentioned to stay within the agreement bounds.  When each of the i servers are configured, if their aggregate utilizations U*i is less than U < 0.58, then the system capacity is planned correctly.  To perform the correct bookkeeping, load classification is done when the request is performed and then based on the classification requests served and delivered bandwidth is charged against the requested virtual server.  Lastly, based on the rates for virtual server i for requests (Ri) and delivered bandwidth (Wi), the control loop achieves the degree of content degradation necessary to keep the utilization of that virtual server at the proper level, preventing overload.

In service differentiation, the goal is to support a number of different clients at different service levels (lower priority clients are degraded first).  In [3], if there are m priority levels, where 1 is the highest priority, capacity of the utilization level of that virtual server is available to clients in priority order.  For the purposes of their research, [3] had two service levels, premium and basic, where premium was guaranteed service and basic was not guaranteed service.

Lastly, in sharing excess capacity, if the load on one server exceeds the maximum capacity C, then the server under overload may temporarily utilize the resources of under utilized virtual servers.  This requires only a simple modification to the control theory loop.

IV. Conclusion

In this survey, we presented information on burstiness in network traffic and how it affects service times.  We also showed how autonomic systems can provision themselves to handle the dynamic workloads.  Dynamic provisioning in multi-tier applications raises some interesting and unique challenges.  As distributed systems become more complex, the techniques surveyed in this paper will become more useful and relevant.

References

[1]     M.C. Huebscher, J.A McCann.  A survey of autonomic computing: Degrees, models, and applications.  ACM Computing Surveys, 40(3), 2008.
[2]     J. Chen, G Soundararajan, C. Amza. Autonomic Provisioning of Backend Databases in Dynamic Content Web Servers. Proc. of IEEE ICAC, 2006.
[3]     T. Abdelzaher, K.G. Shin, N. Bhatti. Performance Guarantees for Web Server End-Systems: A Control-Theoretical Approach. IEEE Transactions on Parallel and Distributed Systems, 13(1), 2002.
[4]     N. Mi, G. Casale, L. Cherkasova, M. Smirini. Burstiness in multi-tier applications: Symptoms, causes, and new models. Proc. of ACM/IFIP/USENIX Middleware, 2008.
[5]     B. Urgaonkar, P. Shenoy, A. Chandra, P. Goyal, and T. Wood. Agile dynamic provisioning of multi-tier Internet applications. ACM Trans. on Autonomous and Adaptive Systems, 3(1):1-39, 2008.
[6]     P. Padala, K.-Y. Hou, K. G. Shin, X. Zhu, M. Uysal, Z. Wang, S. Singhal, and A. Merchant. Automated control of multiple virtualized resources. Proc. of EuroSys, 2009.
[7]     P. Lama and X. Zhou. Autonomic provisioning with self-adaptive neural fuzzy control for end-to-end delay guarantee. Proc. IEEE/ACM MASCOTS, pages 151-160, 2010.
[8]     D. Jiang, G. Pierre, and C.-H. Chi. Autonomous resource provisioning for multi-service web applications. Proc. ACM WWW, 2010.
[9]     L. Kleinrock. Queuing Systems, Volume 2: Computer Applications. John Wiley and Sons, Inc. 1976.
[10]  B. Urgaonkar, G. Pacifici, G. Shenoy, P. Spreitzer, M. and A. Tantawi. An analytical model for multi-tier Internet services and its applications. Proc. of ACM ICMMCS.  Banff, Canada, 2005.

Normally, I think that simpler is better. I enjoy simple things and not just necessarily things like the smell of cut grass, an ice cold beer at a friends BBQ, the first snowfall of winter or reading a book. After all, Occam was on to something (the law of succinctness is a principle which generally recommends selecting the competing hypothesis that makes the fewest new assumptions, when the hypotheses are equal in other respects). Simple is good – less moving parts, less things to break.

I also enjoy simple software and hardware interfaces. Things that I can just pick up and know instantly how to use without reading an instruction manual. Something so simple that Grandma could use it. Apple products always have incredibly simple, unified interfaces: “One Interface to rule them all, One Interface to find them, One Interface to bring them all, and in the darkness bind them.” Simple people living in a simple world. However, simple does NOT imply intuitive.

Ever since the dawn of the electronics age, electronics have had buttons or some sort of interface that had something you could push, pull, or manipulate in some other fashion. Now, there are rumors that iPad2 and iPhone5 will not have home buttons.  In Johnathan Geller’s post:

“We just got some pretty wild information … while it’s hard to believe at first, it does make sense. … The iPad will be losing the home button. … Instead of button taps, you will use new multitouch gestures to navigate to the home screen and … launch the app switcher.
We’re told that this change will make its way over to the iPhone as well. … Apple employees are already testing iPads and iPhones with no home buttons on the Apple campus. … Steve Jobs didn’t want any physical buttons on the original iPhone … it looks like he may soon get his wish.”

So what will be replacing the home button?  In iOS 4.3, which was seeded to developers yesterday, there are new gestures that be done with four or five fingers.  This is particularly a stretch since previous iOS releases supported UIGestureRecognizer to simplify recognizing things like taps, pinch-in and pinch-out.  You could customize the number of fingers needed to perform the gesture and this is simply an extension of existing functionality.  In iOS 4.3, a four or five finger pinch brings you to the home screen,  a swipe up or down reveals the multi-tasking bar and a swipe left or right allows switching between apps.

I am going to do what a devoted Applephite would never do and disagree with what Steve wants.  I think that this is a bad decision because, unlike Steve, regular users actually like buttons!  They like the tactile feel of pushing something, the affirmative “click” that something was done or something will happen.  Consider some software that would process information for whole minutes at a time without providing feedback in the form of a spinner or a progress bar.  Most users would get fed up and try to quit the application.  Without the feedback, user’s may not know what to do.  While these gestures may be fine for people who have been around technology their whole life (think GenY and younger), there are a lot of users who would have problems picking  up the device and straight away being able to use it.  I would even go so far to say that they may never discover some of the features without reading the manual or browsing forums for tips.  Apple has always pride themselves, on simple AND intuitive, easy to use software.  I don’t think regular users are ready for this.

To make my point even clearer, there are still people I know with iOS 4.2 that don’t know that double-tapping the home button brings up the task bar.  They literally have over 75 applications “running” and if it weren’t for me, they would have continued on into their own blissful world, not knowing of that functionality.  And that’s WITH a button.  These gestures should be included in the software in addition so user’s can have their choice of methods of how they want to interact with the device.

Usability aside, how would we perform operations such as recovering crashed phones?

Personally, I would rather see support for a 4G network and WiFi-less FaceTime support.  Although, who knows what the new feature set will be because apparently iOS 4.3 drops support for arm6 (3G).

As engineers, we should attempt to cross the boundary of developers vs. front-end UI design engineers. Typically, people who write code are not very good UI engineers because they just don’t have the experience. It isn’t that we want to make a bad interface, we are just very accustomed to using standard UI components. However, the standard UI components can’t always get the job done in the most effective or user friendly manner. This was precisely the case when I needed to come up with a quick, intuitive way to filter information in one of my iPhone applications.

The horizontal scroll wheel is great because it is built out of standard UI components (UIImageView and UIScrollView) and there is no subclassing to be done to make the widget work. It can be dropped into any application. There is little code to support the layout and generation of the scroll wheel, and all layout calculations are done dynamically so you can have as many or as few items in the list as desired. Also, you can easily create additional value with the audio framework and Core Animation that is extremely simple to do.

For users, it is great because it is an easy to use and understand, quick method to filter a UITableView. The component requires no explanation. A sign of good UI design is a WYSIWYG type approach where the interface is so intuitive it is a joy to use. Create components that users can’t stop playing with.

Let’s get started already. By the way, this tutorial assumes you know Objective-C, Cocoa and basic programming principles. I welcome feedback on any of the code.

ScrollWheel.h

#import <UIKit/UIKit.h>;
#import "ChannelCategory.h"
#import "NSArray+FirstObject.h"
#import "Colors.h"
#import "Debugger.h"

#define SCROLL_WHEEL_CATEGORY_CHANGED @"ScrollWheelCategoryChanged"
#define SCROLL_WHEEL_CATEGORY_ADDED @"ScrollWheelCategoryAdded"

@interface CategoryScrollWheel : UIView <UIScrollViewDelegate> {
  IBOutlet UIScrollView *_scrollView;
}

@property (nonatomic, retain) IBOutlet UIScrollView *_scrollView;

- (void) setupCategories: (NSArray *) categories;
- (void) scrollToButton: (id) sender;
- (void) rebuildCategories;
- (NSArray *) loadNewsCategories;
@end

ScrollWheel.m

#import "CategoryScrollWheel.h"

@implementation CategoryScrollWheel

@synthesize _scrollView;

- (id)initWithFrame:(CGRect)frame {
  if ((self = [super initWithFrame:frame])) {
    // Initialization code
  }
  return self;
}

- (void) rebuildCategories {
  // release the previous wheel and alloc a new one

  [_scrollView release], _scrollView = nil;
  _scrollView = [[UIScrollView alloc] init];

  // reload the categories into the scroll wheel

  [self setupCategories: [NSArray arrayWithArray: [self loadNewsCategories]]];
}

- (NSArray *) loadNewsCategories {
  NSManagedObjectContext *managedObjectContext = [(RSSAppDelegate *)[[UIApplication sharedApplication] delegate] managedObjectContext];

  NSFetchRequest *request = [[NSFetchRequest alloc] init];
  NSError *error;
  NSArray *fetchResults;
  NSSortDescriptor *sortDescriptor = [[NSSortDescriptor alloc] initWithKey:@"name" ascending:NO];
  NSArray *sortDescriptors = [[NSArray alloc] initWithObjects: sortDescriptor, nil];

  [request setEntity: [NSEntityDescription entityForName:@"ChannelCategory" inManagedObjectContext: managedObjectContext]];
  [request setSortDescriptors: sortDescriptors];

  if ((fetchResults = [managedObjectContext executeFetchRequest: request error: &amp;error]) == nil) {
    ALog("%@", error);
    [request release], request = nil;
    [sortDescriptor release], sortDescriptor = nil;
    [sortDescriptors release], sortDescriptors = nil;
    return nil;
  }

  [sortDescriptor release], sortDescriptor = nil;
  [sortDescriptors release], sortDescriptors = nil;

  if([fetchResults count] == 0) {
    // no feeds to refresh
    [request release], request = nil;
    return nil;
  }
  else {
    return fetchResults;
  }
}

- (void) setupCategories: (NSArray *) categories {
  // our variable x will keep track of how far our scroll view extends
  // we need to add a half scroll view width to get the arrow in the middle to
  // be able to center up

  double x = ([self _scrollView].frame.size.width / 2);
  double lastHoldover = 0;
  
  for(ChannelCategory *category in categories) {
    UIButton *button = [[UIButton alloc] init];
    [button setTitle: [category name] forState: UIControlStateNormal];
    [[button titleLabel] setFont: [UIFont fontWithName: @"Helvetica-Bold" size: 11]];
    [[button titleLabel] setTextColor: UI_COLOR_LIGHT_GREY];
    
    CGRect rect = CGRectMake(x, 0, [[category name] sizeWithFont: [UIFont fontWithName: @"Helvetica-Bold" size: 11]].width, 30);

    if([category isEqual: [categories firstObject]]) {
      x -= (rect.size.width / 2);
      rect.origin.x = x;
    }

    [button setFrame: rect];
    [button addTarget: self action: @selector(scrollToButton:) forControlEvents: UIControlEventTouchUpInside];

    [[self _scrollView] addSubview: button];

    x += button.frame.size.width + 10;

    if([category isEqual: [categories lastObject]]) {
      lastHoldover = (button.frame.size.width / 2);
      // bad hack to lop off the extra 10 on the last item
      x -= 10;
    }

    [button release], button = nil;
  }

  // this adds a half scrollview width to the end of the scrollview

  x += ([self _scrollView].frame.size.width / 2);
  x -= lastHoldover;

  CGSize size = CGSizeMake(x, 30);

  [[self _scrollView] setContentSize: size];
}

- (void)scrollViewDidEndDecelerating:(UIScrollView *)scrollView {
  // we add the offset and half the view together to bring it into line with the
  // arrow in the middle
  double val = [[self _scrollView] contentOffset].x + ([self _scrollView].frame.size.width / 2);

  // loop through and see which button is closest.  snap to that button
  // using scrollToButton

  UIButton *closestButton;
  double closest = 100;

  for (UIButton *view in [[self _scrollView] subviews]) {
    if ([view isKindOfClass:[UIButton class]]) {
      double calculatedValue = abs(view.frame.origin.x -  val);

      if(calculatedValue &lt; closest) {
        closestButton = (UIButton *)view;
        closest = calculatedValue;
      }
    }
  }

  CGPoint offset = closestButton.frame.origin;
  CGRect scrollViewFrame = [[self _scrollView] frame];
  offset.x -= (scrollViewFrame.size.width / 2) - (closestButton.frame.size.width / 2);

  [[self _scrollView] setContentOffset:offset animated:YES];
  [[NSNotificationCenter defaultCenter] postNotificationName: SCROLL_WHEEL_CATEGORY_CHANGED object: [[closestButton titleLabel] text]];
}

- (void) scrollToButton: (id) sender {
  CGPoint offset = ((UIButton *)sender).frame.origin;
  CGRect scrollViewFrame = [[self _scrollView] frame];

  offset.x -= (scrollViewFrame.size.width / 2) - (((UIButton *)sender).frame.size.width / 2);

  [[self _scrollView] setContentOffset:offset animated:YES];
  [[NSNotificationCenter defaultCenter] postNotificationName: SCROLL_WHEEL_CATEGORY_CHANGED object: [[sender titleLabel] text]];
}

/*
// Only override drawRect: if you perform custom drawing.
// An empty implementation adversely affects performance during animation.
- (void)drawRect:(CGRect)rect {
  // Drawing code
}
*/

- (void)dealloc {
  [super dealloc];
}

@end

ScrollWheel.xib

In my ScrollWheel.xib, I have 2 UIImageViews and a UIScrollView. Literally, it is that easy. The image view is meant to create a nice frame around the scroll view giving the illusion of “limited view.” The top UIImageView may even have a small arrow pointing down to indicate which item is currently selected. The UIScrollView is the one referenced in the code above.

So there it is – a neat, clean, compact way of taking standard UI components and turning it into a custom UI to allow for selection of categories. If you have any questions or comments on how to improve the code, please let me know!

All code owned and written by David Stites and published on this blog is licensed under MIT/BSD.