Information Technology

Dial-a-Virus
Hackers strike mobile phones

Context: Computer viruses and worms can be sent over mobile wireless networks almost as easily as text and voice messages, and any device that receives voice or data digitally is vulnerable. Some programs drain devices’ batteries, disable buttons, or assail users with mobile spam; the more malicious ones steal information. David Dagon and his colleagues at the Georgia Institute of Technology and Virginia Polytechnic Institute and State University have created a taxonomy (a systematic classification) of mobile “malware” threats.

Methods and Results: By sorting malware according to how it works, the tax­onomy shows not just what kinds of attacks have occurred but also what kinds are possible. Its categories include the vulnerabili­ties that malware exploits (say, certain layers in a routing network) and the types of problems it causes. All existing malware causes semantic errors, a type of error that orders the mobile system to misbehave. The taxonomy shows that new attacks might exploit another class of errors, syntax errors, that confuse the phone by issuing orders it can’t understand, causing the cell-phone equiva­lent of Microsoft’s Blue Screen of Death.

Why it Matters: While mobile antivirus strategies will draw from their desktop counterparts, mobile protection algorithms will need to be optimized for the lower CPU usage, higher power efficiency, and other idiosyncrasies of small devices. To prepare the best defense, engineers and end users need a map of the routes the enemy might take. That is what the taxonomy provides.

Source: Dagon, D., et al. 2004. Mobile phones as computing devices: the viruses are coming! IEEE Pervasive Computing 3:11–15.

Searching for Squishy Shapes
Vision algorithm models deformable objects

Context: To locate an object in an image, computer-vision algorithms often use mathematical models of the object’s shape. But finding the boundaries of “deformable” objects, like human organs, is difficult, because the model must account for all of the objects’ potential shape alterations. Algorithms that can pick out the edges of stretched or squashed objects are often inefficient; they require users or other algorithms to provide initial estimates of the objects’ positions and orientations. Pedro Felzenszwalb of the University of Chicago has developed a deformable-shape model that helps locate such objects in images quickly and accurately.

Methods and Results: Felzenszwalb’s algorithm is able to represent any two-­dimensional shape that contains no holes. Each shape is modeled by a collection of triangles that approximates the boundary of the undeformed shape. The algorithm assumes that some triangles can be distorted more than others, and that triangle edges at the boundaries of an object tend to coincide with changes in image brightness. To match the model to objects in the image, the algorithm deletes one triangle at a time from the model, transferring the information about its best-fitting deformations and image locations to a neighboring triangle. Once all the triangles are eliminated, the stored information can be used to quickly decide the area in the image that best matches the model. Thus, the algorithm can find the object without searching for every possible location, orientation, or deformation of the model.

Given information about how an object could be represented by triangles, the algorithm finds the object’s boundaries in the image. Given a set of example shapes, the algorithm can also construct a general model for a class of objects, such as hands or leaves.

Why it Matters: Better modeling of ­deformable shapes increases the range of objects that computers running vision algorithms are able to automatically recognize. Felzen­szwalb’s method could thus be important for applications such as medical imaging and surveillance. It is as accurate as the leading methods for finding object boundaries in medical images, but it performs well without initially having to guess the object’s location. Nor does the algorithm require the manual specification of parameters such as the amount of distortion allowed for each part of the shape; instead, it can learn from examples, which makes it easier to use.

Source: Felzenszwalb, P. F. 2005. Representation and detection of deformable shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 27:208–220.

Wireless Lookout
Fast handoff for Wi-Fi networks

Context: People routinely access the Internet via the tens of thousands of Wi-Fi access points dotting airports, university campuses, cafés, and other public places. But a Wi-Fi device can connect to an access point only if it is close by—usually within 100 meters. When a device moves beyond the signal range of one access point, it is “handed off” to a nearer one, a process that disrupts data flow. For someone making a phone call over a Wi-Fi phone or watching live streaming multimedia, a one-second delay during handoff can be highly irritating. Ishwar Ramani and Stefan Savage of the University of California, San Diego, have developed a new approach, called SyncScan, that allows faster handoffs.

Methods and Results: Right now, a Wi-Fi device searches for a new access point only after the signal quality from the one it’s using degrades markedly. Then, the device scans all available wireless channels for beacons broadcast by access points, leaving little bandwidth for other incoming data.

With SyncScan, a Wi-Fi device regularly records the signal strengths of other channels, but it checks them only at the precise times that they are scheduled to transmit beacons. Such timing avoids needless channel switching, so the device receives more of the data being sent to it. It also makes better-timed and better-placed handoffs. In a prototype—a laptop computer running the popular Internet-telephony program Skype—the delay during handoff was reduced a hundredfold to only a few milliseconds. The algorithm is expected to work for all Wi-Fi devices.

Why it Matters: Internet telephony and streaming multimedia are emerging as hot applications in Wi-Fi networks. Wi-Fi phones already exist in Japan and are expected in the United States by this spring, but long handoff delays will discourage their adoption. SyncScan shrinks the handoff delay without the need for hardware upgrades or changes to IEEE 802.11, the most widely deployed standard for wireless networks. Though SyncScan is still not perfectly synchronized, it promises to greatly improve the quality, convenience, and value of communication in Wi-Fi networks.

Source: Ramani, I., and S. Savage. 2005. SyncScan: practical fast handoff for 802.11 infrastructure networks. Proceedings of IEEE Infocom 2005 (in press).

Managing Memos
A smarter interface for e-mail

Context: Many people and businesses rely almost entirely on e-mail to manage diverse transactions. But e-mail programs are optimized to manage messages, not to-do lists. Technologies to make e-mail more useful have tried aggregating messages that have a common header or tagging messages as associated with specific, predefined tasks. A new way to free workers from sifting through copious messages—a machine-learning algorithm that automatically keeps track of tasks, and which e-mails are associated with them—hails from Nicholas Kushmerick at University College Dublin and Tessa Lau at IBM.

Methods and Results: First, the algorithm groups e-mails according to the transactions they’re part of, which it deduces by identifying, say, order numbers or clients’ names. Next, messages are grouped by the events they represent, such as shipping notifications or order confirmations. Combining these two perspectives, the algorithm looks for common patterns, or workflows, that recur across a given set of transactions. For example, e-commerce transactions typically involve order notification, shipping notification, and messages about delayed or modified orders.

On the basis of such patterns, the al­gorithm automatically determines the status of a given transaction. Without requiring user input or manually labeled examples, the algorithm correctly identified the transaction stages represented by 101 out of 111 messages in an e-commerce test set representing 39 transactions by six vendors.

Why it Matters: A 2003 survey of major industries found that more than 90 percent of organizations use e-mail to respond to customer inquiries, and about 70 percent use e-mail for invoicing and contract negotiation. Kushmerick and Lau envision their algorithm as the core of an interface that automatically organizes e-mail by task as easily as by date or sender. By learning workflows, the algorithm can facilitate even specialized processes, which gives it an advantage over techniques that rely on message headers or preformatted content. Eventually, this technique and others like it should help convert cluttered in-boxes into a set of well-oiled workflows.

Source: Kushmerick, N., and T. Lau. 2005. Automated e-mail activity management: an unsupervised learning approach. Proceedings of the 10th International Conference on Intelligent User Interfaces, pp. 67–74.