March 28, 2006— Searching for this thingamajig or that doohickey? A new search engine could help you find the item in an online catalog not by its name or product number, but by its shape.
The 3D-Seek search engine, being developed by Purdue University and software start-up Imaginestics in West Lafayette, Ind., uses sophisticated pattern recognition programs to match sketches or finished illustrations with the right three-dimensional image file of an industrial part.
"The neat thing is that you can search 3D with 3D. You can search using a sketch or an image or using a 3-D part," said Karthik Ramani, the director of Purdue Research and Education Center for Information Systems in Engineering and the chief scientist at Imaginestics.
Although the software is initially geared toward the manufacturing industry, it could find its way to the ordinary consumer, helping shoppers at hardware or auto parts stores locate the correct component based on a freehand sketch.
Development of the software arose as a solution to a common problem in manufacturing: too many parts and no efficient way to find them.
Each new product that comes to market — whether it's a vehicle, a vacuum cleaner, or a vending machine — is made up of many different parts that are drawn in three dimensions using computer-aided design software.
Once the part is drawn and manufactured, the image file is often stored in a database with millions of other part drawings.
Those parts can be difficult to track down for use later by another designer in the company simply because there is no industry standard for naming parts.
"There are millions of parts. Which one is similar? You don't know based on the file name. You have to know specifically that this person has done this thing. It's not very easy," said Xiaoping Qian, assistant professor at the Illinois Institute of Technology in Chicago.
Oftentimes, designers end up drawing a duplicate part without knowing it, which wastes time and money.
With 3D-Seek, a designer uses a mouse or stylus to sketch the part they need. They can specify different viewpoints, such as top view or side view.
Software in the search engine plots the sketch and, using sophisticated calculation formulas, generates a list of unique numbers based on the object's geometry.
Then the search engine pulls up a list of parts that have a list of similar numbers. The user can refine the search based on the query results to get closer to the exact part.
Although the 3D-Seek catalog contains just 6,000 parts on a Web site that the company has invited the public to test out, the software is capable of sifting through millions of components.
Ramani is working with manufacturers and Imaginestics to develop new and improved versions that will produce more accurate results.
(http://dsc.discovery.com/news/briefs/20060327/doodlesearch_tec_print.html)
Tuesday, March 28, 2006
Running all tests within an Eclipse project by Alex Blewitt
This is an repost of my blog entry which itself was an extension of a hint posted by my good friend Björn Mårtensson that allowed all tests to be run inside Eclipse.
If you've ever done any programming inside Eclipse, and wanted to use a suite of JUnit tests , then you'll know that you either have to run each test individually inside Eclipse, or create a test suite (normally called AllTests ) that encompasses all the tests you want to run. Having to manually update that class each time you want to run a new test is less than productive use of your time, and besides which, may result in you forgetting to add tests when they're created.
Fortunately, you don't need to specify a hard-coded list of tests to run; you can run all tests in an Eclipse project in one go. All you need to do is calculate the list of classes, and then pass those into the standard test runner and get the answer back again. And there's a really easy way of doing this using the TestCollector interface (and the ClassPathTestCollector implementation).
I've adapted Björn's original example to include a check for non- abstract classes, and also to allow the test to be run in a plugin as well as in Eclipse. This is necessary when doing Eclipse platform development, since your code may assume a particular behaviour of (say) Plugin.getStateLocation() , which wouldn't be available if you were just using ordinary JUnit testing. The AllTests looks for *Test on the classpath, filtering out *PlatformTest if not running as an Eclipse plugin. It does this by providing a second TestCollector implementation; if you want to copy and paste this code on non-plugin projects, just delete this implementation.
Owing to the fact that it's not possible (AFAIK) to determine the bundle name from the class that is being run (especially from static methods), the code makes the assumption that the package that contains the AllTests class is the same name as the plugin. So if you wanted to test the org.example.foo plugin, then you'd put it into the org.example.foo package. This can be changed in the source code.
The latest version should be available at AllTests.java but at the time of writing, the public CVS web repository is several days behind the HEAD that's been checked in, so YMMV. (Maybe this is why they're encouraging people to switch over to Subversion...) In the meantime, here's the contents of the code. It's released under the EPL, so you can use it in your own projects:
// Copyright (c) 2006 Alex Blewitt
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// which accompanies this distribution, and is available at
// http://www.eclipse.org/legal/epl-v10.html
//
// Contributors:
// Alex Blewitt - Initial API and implementation
//
package org.rcpapps.base;
import java.lang.reflect.Modifier;
import java.net.URL;
import java.util.Enumeration;
import java.util.Vector;
import junit.framework.Test;
import junit.framework.TestSuite;
import junit.runner.ClassPathTestCollector;
import junit.runner.TestCollector;
import org.eclipse.core.runtime.Platform;
/**
* Run all the tests in this project, either computed from the classpath or from
* the bundlepath. To use this as-is, drop it into a non-default package that
* has the same name as the plugin. For example, if the plugin is called
*
org.example.foo
, this should be placed in a package
*
org.example.foo
, and all tests should live under the
*
org.example.foo
package structure (either directly, or in any
* subpackage). By default this will include all non-abstract classes named
*
XxxTest
, excluding
XxxPlatformTest
if running
* outside of the platform.
*/
public class AllTests {
/**
* Detects classes from the bundle PLUGIN_NAME's entries. Uses
*
bundle.findEntries
to obtain a list of classes that live
* in the specified PACKAGE_NAME, and adds those to the test path, providing
* that they are {@link AllTests#isValidTest(String, boolean) valid}.
*/
private static class BundleTestDetector implements TestCollector {
/*
* @see junit.runner.TestCollector#collectTests()
*/
public Enumeration collectTests() {
final Vector tests = new Vector();
try {
Enumeration entries = Platform.getBundle(PLUGIN_NAME).findEntries("/", "*" + SUFFIX + ".class", true);
while (entries.hasMoreElements()) {
URL entry = (URL) entries.nextElement();
// Change the URLs to have Java class names
String path = entry.getPath().replace('/', '.');
int start = path.indexOf(PACKAGE_NAME);
String name = path.substring(start, path.length()
- ".class".length());
if (isValidTest(name, true)) {
tests.add(name);
}
}
} catch (Exception e) {
// If we get here, the Platform isn't installed and so we fail
// quietly. This isn't a problem; we might be outside of the
// Platform framework and just running tests locally. It's not
// even worth printing anything out to the error log as it would
// just confuse people investigating stack traces etc.
}
return tests.elements();
}
}
/**
* Searches the current classpath for tests, which are those ending with
* SUFFIX, excluding those which end in IN_CONTAINER_SUFFIX, providing that
* they are {@link AllTests#isValidTest(String, boolean) valid}.
*/
private static class ClassFileDetector extends ClassPathTestCollector {
/*
* @see junit.runner.ClassPathTestCollector#isTestClass(java.lang.String)
*/
protected boolean isTestClass(String classFileName) {
return classFileName.endsWith(SUFFIX + ".class")
&& isValidTest(classNameFromFile(classFileName), false);
}
}
/**
* All tests should end in XxxTest
*/
public static final String SUFFIX = "Test";
/**
* All in-container tests should end in XxxPlatformTest
*/
public static final String IN_CONTAINER_SUFFIX = "Platform" + SUFFIX;
/**
* The base package name of the tests to run. This defaults to the name of
* the package that the AllTests class is in for ease of management but may
* be trivially changed if required. Note that at least some identifiable
* part must be provided here (so default package names are not allowed)
* since the URL that comes up in the bundle entries have a prefix that is
* not detectable automatically. Even if this is "org" or "com" that should
* be enough.
*/
public static final String PACKAGE_NAME = AllTests.class.getPackage()
.getName();
/**
* The name of the plugin to search if the platform is loaded. This defaults
* to the name of the package that the AllTests class is in for ease of
* management but may be trivially changed if required.
*/
public static final String PLUGIN_NAME = AllTests.class.getPackage()
.getName();
/**
* Add the tests reported by collector to the list of tests to run
* @param collector the test collector to run
* @param suite the suite to add the tests to
*/
private static void addTestsToSuite(TestCollector collector, TestSuite suite) {
Enumeration e = collector.collectTests();
while (e.hasMoreElements()) {
String name = (String) e.nextElement();
try {
suite.addTestSuite(Class.forName(name));
} catch (ClassNotFoundException e1) {
System.err.println("Cannot load test: " + e1);
}
}
}
/**
* Is the test a valid test?
* @param name the name of the test
* @param inContainer true if we want to include the inContainer tests
* @return true if the name is a valid class (can be loaded), that it is not
* abstract, and that it ends with SUFFIX, and that either
* inContainer tests are to be included or the name does not end
* with IN_CONTAINER_SUFFIX
*/
private static boolean isValidTest(String name, boolean inContainer) {
try {
return name.endsWith(SUFFIX)
&& (inContainer || !name.endsWith(IN_CONTAINER_SUFFIX))
&& ((Class.forName(name).getModifiers() & Modifier.ABSTRACT) == 0);
} catch (ClassNotFoundException e) {
System.err.println(e.toString());
return false;
}
}
/**
* Return all the tests. If we're in a platform, return everything. If not,
* we return those tests that end in SUFFIX but excluding those ending in
* IN_CONTAINER_SUFFIX.
* @return a suite of tests for JUnit to run
* @throws Error if there are no tests to run.
*/
public static Test suite() {
TestSuite suite = new TestSuite(AllTests.class.getName());
addTestsToSuite(new ClassFileDetector(), suite);
addTestsToSuite(new BundleTestDetector(), suite);
if (suite.countTestCases() == 0) {
throw new Error("There are no test cases to run");
} else {
return suite;
}
}
}
(http://www.eclipsezone.com/eclipse/forums/t65337.html)
If you've ever done any programming inside Eclipse, and wanted to use a suite of JUnit tests , then you'll know that you either have to run each test individually inside Eclipse, or create a test suite (normally called AllTests ) that encompasses all the tests you want to run. Having to manually update that class each time you want to run a new test is less than productive use of your time, and besides which, may result in you forgetting to add tests when they're created.
Fortunately, you don't need to specify a hard-coded list of tests to run; you can run all tests in an Eclipse project in one go. All you need to do is calculate the list of classes, and then pass those into the standard test runner and get the answer back again. And there's a really easy way of doing this using the TestCollector interface (and the ClassPathTestCollector implementation).
I've adapted Björn's original example to include a check for non- abstract classes, and also to allow the test to be run in a plugin as well as in Eclipse. This is necessary when doing Eclipse platform development, since your code may assume a particular behaviour of (say) Plugin.getStateLocation() , which wouldn't be available if you were just using ordinary JUnit testing. The AllTests looks for *Test on the classpath, filtering out *PlatformTest if not running as an Eclipse plugin. It does this by providing a second TestCollector implementation; if you want to copy and paste this code on non-plugin projects, just delete this implementation.
Owing to the fact that it's not possible (AFAIK) to determine the bundle name from the class that is being run (especially from static methods), the code makes the assumption that the package that contains the AllTests class is the same name as the plugin. So if you wanted to test the org.example.foo plugin, then you'd put it into the org.example.foo package. This can be changed in the source code.
The latest version should be available at AllTests.java but at the time of writing, the public CVS web repository is several days behind the HEAD that's been checked in, so YMMV. (Maybe this is why they're encouraging people to switch over to Subversion...) In the meantime, here's the contents of the code. It's released under the EPL, so you can use it in your own projects:
// Copyright (c) 2006 Alex Blewitt
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// which accompanies this distribution, and is available at
// http://www.eclipse.org/legal/epl-v10.html
//
// Contributors:
// Alex Blewitt - Initial API and implementation
//
package org.rcpapps.base;
import java.lang.reflect.Modifier;
import java.net.URL;
import java.util.Enumeration;
import java.util.Vector;
import junit.framework.Test;
import junit.framework.TestSuite;
import junit.runner.ClassPathTestCollector;
import junit.runner.TestCollector;
import org.eclipse.core.runtime.Platform;
/**
* Run all the tests in this project, either computed from the classpath or from
* the bundlepath. To use this as-is, drop it into a non-default package that
* has the same name as the plugin. For example, if the plugin is called
*
org.example.foo
, this should be placed in a package
*
org.example.foo
, and all tests should live under the
*
org.example.foo
package structure (either directly, or in any
* subpackage). By default this will include all non-abstract classes named
*
XxxTest
, excluding
XxxPlatformTest
if running
* outside of the platform.
*/
public class AllTests {
/**
* Detects classes from the bundle PLUGIN_NAME's entries. Uses
*
bundle.findEntries
to obtain a list of classes that live
* in the specified PACKAGE_NAME, and adds those to the test path, providing
* that they are {@link AllTests#isValidTest(String, boolean) valid}.
*/
private static class BundleTestDetector implements TestCollector {
/*
* @see junit.runner.TestCollector#collectTests()
*/
public Enumeration collectTests() {
final Vector tests = new Vector();
try {
Enumeration entries = Platform.getBundle(PLUGIN_NAME).findEntries("/", "*" + SUFFIX + ".class", true);
while (entries.hasMoreElements()) {
URL entry = (URL) entries.nextElement();
// Change the URLs to have Java class names
String path = entry.getPath().replace('/', '.');
int start = path.indexOf(PACKAGE_NAME);
String name = path.substring(start, path.length()
- ".class".length());
if (isValidTest(name, true)) {
tests.add(name);
}
}
} catch (Exception e) {
// If we get here, the Platform isn't installed and so we fail
// quietly. This isn't a problem; we might be outside of the
// Platform framework and just running tests locally. It's not
// even worth printing anything out to the error log as it would
// just confuse people investigating stack traces etc.
}
return tests.elements();
}
}
/**
* Searches the current classpath for tests, which are those ending with
* SUFFIX, excluding those which end in IN_CONTAINER_SUFFIX, providing that
* they are {@link AllTests#isValidTest(String, boolean) valid}.
*/
private static class ClassFileDetector extends ClassPathTestCollector {
/*
* @see junit.runner.ClassPathTestCollector#isTestClass(java.lang.String)
*/
protected boolean isTestClass(String classFileName) {
return classFileName.endsWith(SUFFIX + ".class")
&& isValidTest(classNameFromFile(classFileName), false);
}
}
/**
* All tests should end in XxxTest
*/
public static final String SUFFIX = "Test";
/**
* All in-container tests should end in XxxPlatformTest
*/
public static final String IN_CONTAINER_SUFFIX = "Platform" + SUFFIX;
/**
* The base package name of the tests to run. This defaults to the name of
* the package that the AllTests class is in for ease of management but may
* be trivially changed if required. Note that at least some identifiable
* part must be provided here (so default package names are not allowed)
* since the URL that comes up in the bundle entries have a prefix that is
* not detectable automatically. Even if this is "org" or "com" that should
* be enough.
*/
public static final String PACKAGE_NAME = AllTests.class.getPackage()
.getName();
/**
* The name of the plugin to search if the platform is loaded. This defaults
* to the name of the package that the AllTests class is in for ease of
* management but may be trivially changed if required.
*/
public static final String PLUGIN_NAME = AllTests.class.getPackage()
.getName();
/**
* Add the tests reported by collector to the list of tests to run
* @param collector the test collector to run
* @param suite the suite to add the tests to
*/
private static void addTestsToSuite(TestCollector collector, TestSuite suite) {
Enumeration e = collector.collectTests();
while (e.hasMoreElements()) {
String name = (String) e.nextElement();
try {
suite.addTestSuite(Class.forName(name));
} catch (ClassNotFoundException e1) {
System.err.println("Cannot load test: " + e1);
}
}
}
/**
* Is the test a valid test?
* @param name the name of the test
* @param inContainer true if we want to include the inContainer tests
* @return true if the name is a valid class (can be loaded), that it is not
* abstract, and that it ends with SUFFIX, and that either
* inContainer tests are to be included or the name does not end
* with IN_CONTAINER_SUFFIX
*/
private static boolean isValidTest(String name, boolean inContainer) {
try {
return name.endsWith(SUFFIX)
&& (inContainer || !name.endsWith(IN_CONTAINER_SUFFIX))
&& ((Class.forName(name).getModifiers() & Modifier.ABSTRACT) == 0);
} catch (ClassNotFoundException e) {
System.err.println(e.toString());
return false;
}
}
/**
* Return all the tests. If we're in a platform, return everything. If not,
* we return those tests that end in SUFFIX but excluding those ending in
* IN_CONTAINER_SUFFIX.
* @return a suite of tests for JUnit to run
* @throws Error if there are no tests to run.
*/
public static Test suite() {
TestSuite suite = new TestSuite(AllTests.class.getName());
addTestsToSuite(new ClassFileDetector(), suite);
addTestsToSuite(new BundleTestDetector(), suite);
if (suite.countTestCases() == 0) {
throw new Error("There are no test cases to run");
} else {
return suite;
}
}
}
(http://www.eclipsezone.com/eclipse/forums/t65337.html)
Monday, March 20, 2006
RFID Viruses and Worms by Melanie R. Rieback, Patrick N. D. Simpson, Bruno Crispo, Andrew S. Tanenbaum
Melanie R. Rieback, Patrick N. D. Simpson, Bruno Crispo, Andrew S. Tanenbaum
Department of Computer Science , Vrije Universiteit Amsterdam
info@rfidvirus.org
280 papers were submitted; 23 were accepted, and we won the Best Paper Award for Most Impact.
This work has received massive worldwide publicity.
This page describes our work on RFID Malware: RFID exploits, RFID worms, and RFID viruses.
--------------------------------------------------------------------------------
Introduction to RFID Technology
--------------------------------------------------------------------------------
Radio Frequency Identification (RFID) is the latest phase in the decades-old trend of the miniaturization of computers. RFID transponders are tiny resource-limited computers that do not have a battery that needs periodic replacement. RFID tags are inductively powered by their external reading devices, called RFID readers. Once the RFID tag is activated, the tag decodes the incoming query and produces an appropriate response by using the energy of the incoming radio wave to power the chip long enough to respond. RFID tags can do a limited amount of processing, and have a small amount (<1024 bits) of storage.
RFID tags are useful for a huge variety of applications. Some of these applications include: supply chain management, automated payment, physical access control, counterfeit prevention, airline baggage management, and smart homes and offices. RFID tags are also implanted in all kinds of personal and consumer goods, for example, passports, partially assembled cars, frozen dinners, ski-lift passes, clothing, EZ-Pass toll collection devices, and public transportation tickets. Implantable RFID tags for animals allow concerned owners to label their pets and livestock. Verichip Corp. has also created a slightly adapted implantable RFID chip, the size of a grain of rice, for use in humans. Since its introduction, the Verichip was approved by the U.S. Food and Drug Administration, and this tiny chip is currently deployed in both commercial and medical systems. A great deal of information is available on RFID technology. Some introductory Web pages are listed here.
--------------------------------------------------------------------------------
RFID Threats
--------------------------------------------------------------------------------
Unfortunately, businesses and governments are not the only ones interested in RFID. Civil liberties groups, hackers and criminals are also keenly interested in this new development, albeit for very different reasons. Civil liberties groups are concerned about RFID technology being used to invade people's privacy; RFID tags enable unethical individuals to snoop on people and surreptitiously collect data on them without their approval or even knowledge. For example, RFID-enabled public transit tickets could allow public transit managers to compile a dossier listing all of a person's travels in the past year -- information which may be of interest to the police, divorce lawyers, and others.
However, privacy is not the focus of this website and will not be discussed further below. On the other hand, we are intensely concerned about privacy in an RFID-enabled world and have built an entire sister website about a device we have constructed, called the RFID Guardian, which could potentially help people protect their privacy from RFID snooping in the future. Those interested in RFID and privacy might want to check it out at www.rfidguardian.org. The website even includes a video of the prototype RFID Guardian in action.
A completely different category of threats arises when hackers or criminals cause valid RFID tags to behave in unexpected (and generally malicious) ways. Typically, computer-bound or mobile RFID readers query RFID tags for their unique identifier or on-tag data, which often serves as a database key or launches some real-world activity. For example, when an RFID reader at a supermarket checkout counter reads the tag on a product, the software driving it could add the item scanned to the list of the customer's purchases, tallying up the total after all products have been scanned.
Here is where the trouble comes in. Up until now, everyone working on RFID technology has tacitly assumed that the mere act of scanning an RFID tag cannot modify back-end software, and certainly not in a malicious way. Unfortunately, they are wrong. In our research, we have discovered that if certain vulnerabilities exist in the RFID software, an RFID tag can be (intentionall) infected with a virus and this virus can infect the backend database used by the RFID software. From there it can be easily spread to other RFID tags. No one thought this possible until now. Later in this website we provide all the details on how to do this and how to defend against it in order to warn the designers of RFID systems not to deploy vulnerable systems.
While we have some hesitation in giving the "bad guys" precise information on how to infect RFID tags, it has been our experience that when talking to people in charge of RFID systems, they often dismiss security concerns as academic, unrealistic, and unworthy of spending any money on countering, as these threats are merely "theoretical." By making code for RFID "malware" publicly available, we hope to convince them that the problem is serious and had better be dealt with, and fast. It is a lot better to lock the barn door while the prize race horse is still inside than to deal with the consequences of not doing so afterwards.
--------------------------------------------------------------------------------
Real-World Scenarios
--------------------------------------------------------------------------------
To make clear what kinds of problems might arise from RFID hacking by amateurs or criminals, let us consider three possible and all-too-realistic scenarios.
A prankster goes to a supermarket that scans the purchases in its customers' shopping carts using the RFID chips affixed to the products instead of their bar codes. Many supermarkets have plans in this direction because RFID scans are faster (and in some cases can be done by the customers, eliminating the expense of having cashiers). The prankster selects, scans, and pays for a nice jar of chunk-style peanut butter that has an RFID tag attached to it. Upon getting it home, he removes or destroys the RFID tag. Then he takes a blank RFID tag he has purchased and writes a exploit on it using his home computer and commercially available equipment for writing RFID tags. He then attaches the infected tag to the jar of peanut butter, brings it back to the supermarket, heads directly for the checkout counter, and pays for it again. Unfortunately, this time when the jar is scanned, the virus on its tag infects the supermarket's product database, potentially wreaking all kinds of havoc such as changing prices.
Emboldened by his success at the supermarket, the prankster decides to unwittingly enlist his cat in the fun. The cat has a subdermal pet ID tag, which the attacker rewrites with a virus using commercially available equipment. He then goes to a veterinarian (or the ASPCA), claims it is stray cat and asks for a cat scan. Bingo! The database is infected. Since the vet (or ASPCA) uses this database when creating tags for newly-tagged animals, these new tags can also be infected. When they are later scanned for whatever reason, that database is infected, and so on. Unlike a biological virus, which jumps from animal to animal, an RFID virus spread this way jumps from animal to database to animal. The same transmission mechanism that applies to pets also applies to RFID-tagged livestock.
Now we get to the scary part. Some airports are planning to expedite baggage handling by attaching RFID-augmented labels to the suitcases as they are checked in. This makes the labels easier to read at greater distances than the current bar-coded baggage labels. Now consider a malicious traveler who attaches a tiny RFID tag, pre-initialized with a virus, to a random person's suitcase before he checks it in. When the baggage-handling system's RFID reader scans the suitcase at a Y-junction in the conveyor-belt system to determine where to route it, the tag responds with the RFID virus, which could infect the airport's baggage database. Then, all RFID tags produced as new passengers check in later in the day may also be infected. If any of these infected bags transit a hub, they will be rescanned there, thus infecting a different airport. Within a day, hundreds of airport databases all over the world could be infected. Merely infecting other tags is the most benign case. An RFID virus could also carry a payload that did other damage to the database, for example, helping drug smugglers or terrorists hide their baggage from airline and government officials, or intentionally sending baggage destined for Alaska to Argentina to create chaos (e.g., as revenge for a recently fired airline employee).
--------------------------------------------------------------------------------
Technical Details
--------------------------------------------------------------------------------
By now the general outline of the problem should be clear: when an unsuspecting reader scans an infected tag, there is a danger of the tag exploiting a vulnerability in the middleware to cause unwanted actions to occur, which may include infecting the database. Now it is time to go into more detail. The links below give more technical detail about possible attacks and how to prevent them. It is suggested that you read them in order.
(http://www.rfidvirus.org/index.html)
Department of Computer Science , Vrije Universiteit Amsterdam
info@rfidvirus.org
280 papers were submitted; 23 were accepted, and we won the Best Paper Award for Most Impact.
This work has received massive worldwide publicity.
This page describes our work on RFID Malware: RFID exploits, RFID worms, and RFID viruses.
--------------------------------------------------------------------------------
Introduction to RFID Technology
--------------------------------------------------------------------------------
Radio Frequency Identification (RFID) is the latest phase in the decades-old trend of the miniaturization of computers. RFID transponders are tiny resource-limited computers that do not have a battery that needs periodic replacement. RFID tags are inductively powered by their external reading devices, called RFID readers. Once the RFID tag is activated, the tag decodes the incoming query and produces an appropriate response by using the energy of the incoming radio wave to power the chip long enough to respond. RFID tags can do a limited amount of processing, and have a small amount (<1024 bits) of storage.
RFID tags are useful for a huge variety of applications. Some of these applications include: supply chain management, automated payment, physical access control, counterfeit prevention, airline baggage management, and smart homes and offices. RFID tags are also implanted in all kinds of personal and consumer goods, for example, passports, partially assembled cars, frozen dinners, ski-lift passes, clothing, EZ-Pass toll collection devices, and public transportation tickets. Implantable RFID tags for animals allow concerned owners to label their pets and livestock. Verichip Corp. has also created a slightly adapted implantable RFID chip, the size of a grain of rice, for use in humans. Since its introduction, the Verichip was approved by the U.S. Food and Drug Administration, and this tiny chip is currently deployed in both commercial and medical systems. A great deal of information is available on RFID technology. Some introductory Web pages are listed here.
--------------------------------------------------------------------------------
RFID Threats
--------------------------------------------------------------------------------
Unfortunately, businesses and governments are not the only ones interested in RFID. Civil liberties groups, hackers and criminals are also keenly interested in this new development, albeit for very different reasons. Civil liberties groups are concerned about RFID technology being used to invade people's privacy; RFID tags enable unethical individuals to snoop on people and surreptitiously collect data on them without their approval or even knowledge. For example, RFID-enabled public transit tickets could allow public transit managers to compile a dossier listing all of a person's travels in the past year -- information which may be of interest to the police, divorce lawyers, and others.
However, privacy is not the focus of this website and will not be discussed further below. On the other hand, we are intensely concerned about privacy in an RFID-enabled world and have built an entire sister website about a device we have constructed, called the RFID Guardian, which could potentially help people protect their privacy from RFID snooping in the future. Those interested in RFID and privacy might want to check it out at www.rfidguardian.org. The website even includes a video of the prototype RFID Guardian in action.
A completely different category of threats arises when hackers or criminals cause valid RFID tags to behave in unexpected (and generally malicious) ways. Typically, computer-bound or mobile RFID readers query RFID tags for their unique identifier or on-tag data, which often serves as a database key or launches some real-world activity. For example, when an RFID reader at a supermarket checkout counter reads the tag on a product, the software driving it could add the item scanned to the list of the customer's purchases, tallying up the total after all products have been scanned.
Here is where the trouble comes in. Up until now, everyone working on RFID technology has tacitly assumed that the mere act of scanning an RFID tag cannot modify back-end software, and certainly not in a malicious way. Unfortunately, they are wrong. In our research, we have discovered that if certain vulnerabilities exist in the RFID software, an RFID tag can be (intentionall) infected with a virus and this virus can infect the backend database used by the RFID software. From there it can be easily spread to other RFID tags. No one thought this possible until now. Later in this website we provide all the details on how to do this and how to defend against it in order to warn the designers of RFID systems not to deploy vulnerable systems.
While we have some hesitation in giving the "bad guys" precise information on how to infect RFID tags, it has been our experience that when talking to people in charge of RFID systems, they often dismiss security concerns as academic, unrealistic, and unworthy of spending any money on countering, as these threats are merely "theoretical." By making code for RFID "malware" publicly available, we hope to convince them that the problem is serious and had better be dealt with, and fast. It is a lot better to lock the barn door while the prize race horse is still inside than to deal with the consequences of not doing so afterwards.
--------------------------------------------------------------------------------
Real-World Scenarios
--------------------------------------------------------------------------------
To make clear what kinds of problems might arise from RFID hacking by amateurs or criminals, let us consider three possible and all-too-realistic scenarios.
A prankster goes to a supermarket that scans the purchases in its customers' shopping carts using the RFID chips affixed to the products instead of their bar codes. Many supermarkets have plans in this direction because RFID scans are faster (and in some cases can be done by the customers, eliminating the expense of having cashiers). The prankster selects, scans, and pays for a nice jar of chunk-style peanut butter that has an RFID tag attached to it. Upon getting it home, he removes or destroys the RFID tag. Then he takes a blank RFID tag he has purchased and writes a exploit on it using his home computer and commercially available equipment for writing RFID tags. He then attaches the infected tag to the jar of peanut butter, brings it back to the supermarket, heads directly for the checkout counter, and pays for it again. Unfortunately, this time when the jar is scanned, the virus on its tag infects the supermarket's product database, potentially wreaking all kinds of havoc such as changing prices.
Emboldened by his success at the supermarket, the prankster decides to unwittingly enlist his cat in the fun. The cat has a subdermal pet ID tag, which the attacker rewrites with a virus using commercially available equipment. He then goes to a veterinarian (or the ASPCA), claims it is stray cat and asks for a cat scan. Bingo! The database is infected. Since the vet (or ASPCA) uses this database when creating tags for newly-tagged animals, these new tags can also be infected. When they are later scanned for whatever reason, that database is infected, and so on. Unlike a biological virus, which jumps from animal to animal, an RFID virus spread this way jumps from animal to database to animal. The same transmission mechanism that applies to pets also applies to RFID-tagged livestock.
Now we get to the scary part. Some airports are planning to expedite baggage handling by attaching RFID-augmented labels to the suitcases as they are checked in. This makes the labels easier to read at greater distances than the current bar-coded baggage labels. Now consider a malicious traveler who attaches a tiny RFID tag, pre-initialized with a virus, to a random person's suitcase before he checks it in. When the baggage-handling system's RFID reader scans the suitcase at a Y-junction in the conveyor-belt system to determine where to route it, the tag responds with the RFID virus, which could infect the airport's baggage database. Then, all RFID tags produced as new passengers check in later in the day may also be infected. If any of these infected bags transit a hub, they will be rescanned there, thus infecting a different airport. Within a day, hundreds of airport databases all over the world could be infected. Merely infecting other tags is the most benign case. An RFID virus could also carry a payload that did other damage to the database, for example, helping drug smugglers or terrorists hide their baggage from airline and government officials, or intentionally sending baggage destined for Alaska to Argentina to create chaos (e.g., as revenge for a recently fired airline employee).
--------------------------------------------------------------------------------
Technical Details
--------------------------------------------------------------------------------
By now the general outline of the problem should be clear: when an unsuspecting reader scans an infected tag, there is a danger of the tag exploiting a vulnerability in the middleware to cause unwanted actions to occur, which may include infecting the database. Now it is time to go into more detail. The links below give more technical detail about possible attacks and how to prevent them. It is suggested that you read them in order.
(http://www.rfidvirus.org/index.html)
Viruses leap to smart radio tags By Mark Ward - Technology Correspondent, BBC News website
Computer viruses could be about to take a giant leap and start spreading via smart barcodes, warn experts.
Security researchers have infected a Radio Frequency ID tag with a computer virus to show how the technology is vulnerable to malicious hackers.
The researchers warn that RFID tags could help mount many different types of attacks on computer systems.
Makers of radio tag systems were urged by the group to introduce safeguards to guard against RFID-borne bugs.
Cat attack
"This is intended as a wake-up call," said Andrew Tanenbaum, one of the researchers in the computer science department at Amsterdam's Free University that did the work revealing the weaknesses on smart tags.
"We ask the RFID industry to design systems that are secure," he said.
RFID tags are essentially smart barcodes that replace the familiar lines with a small amount of computer memory, a tiny processing unit and a radio. Information is downloaded into the tag and read off it via radio.
Many large companies are keen to use the RFID tags because they will help keep track of the goods they are shipping from warehouses out to stores or regional offices. Currently RFID tags are relatively expensive so most are used to log what is in boxes of goods rather than to label individual items.
However, many expect the smart tags to become ubiquitous as the price of making the devices falls.
In their research paper Mr Tanenbaum and his colleagues Melanie Rieback and Bruno Crispo detail how to use RFID tags to spread viruses and subvert corporate databases.
"Everyone working on RFID technology has tacitly assumed that the mere act of scanning an RFID tag cannot modify back-end software and certainly not in a malicious way. Unfortunately, they are wrong," wrote the trio in their research paper.
The researchers showed how to get round the limited computational abilities of the smart tags to use them as an attack vector and corrupt databases holding information about what a company has in storage. To test out the theory the group created a virus for a smart tag that used only 127 characters, uploaded it and watched it in action.
Mikko Hypponen, chief research officer at anti-virus firm F-Secure, said: "RFIDs with embedded computers are suspectible to basically all the same threats any other computers are. Unfortunately."
If viruses do appear in smart tags, said the researchers, they are likely to cause problems for companies that read data off the tags. They speculated that consumer activist groups could use smart tags viruses to cause havoc at stores they are targeting.
In some cases, said the researchers, viruses could be spread by household pets such as cats and dogs that are injected with the tags to help identify their owner.
The researchers urged companies working on RFID systems to start thinking seriously about security measures to protect against future threats.
(www.bbc.com - Wednesday, 15 March 2006, 18:02 GMT)
Security researchers have infected a Radio Frequency ID tag with a computer virus to show how the technology is vulnerable to malicious hackers.
The researchers warn that RFID tags could help mount many different types of attacks on computer systems.
Makers of radio tag systems were urged by the group to introduce safeguards to guard against RFID-borne bugs.
Cat attack
"This is intended as a wake-up call," said Andrew Tanenbaum, one of the researchers in the computer science department at Amsterdam's Free University that did the work revealing the weaknesses on smart tags.
"We ask the RFID industry to design systems that are secure," he said.
RFID tags are essentially smart barcodes that replace the familiar lines with a small amount of computer memory, a tiny processing unit and a radio. Information is downloaded into the tag and read off it via radio.
Many large companies are keen to use the RFID tags because they will help keep track of the goods they are shipping from warehouses out to stores or regional offices. Currently RFID tags are relatively expensive so most are used to log what is in boxes of goods rather than to label individual items.
However, many expect the smart tags to become ubiquitous as the price of making the devices falls.
In their research paper Mr Tanenbaum and his colleagues Melanie Rieback and Bruno Crispo detail how to use RFID tags to spread viruses and subvert corporate databases.
"Everyone working on RFID technology has tacitly assumed that the mere act of scanning an RFID tag cannot modify back-end software and certainly not in a malicious way. Unfortunately, they are wrong," wrote the trio in their research paper.
The researchers showed how to get round the limited computational abilities of the smart tags to use them as an attack vector and corrupt databases holding information about what a company has in storage. To test out the theory the group created a virus for a smart tag that used only 127 characters, uploaded it and watched it in action.
Mikko Hypponen, chief research officer at anti-virus firm F-Secure, said: "RFIDs with embedded computers are suspectible to basically all the same threats any other computers are. Unfortunately."
If viruses do appear in smart tags, said the researchers, they are likely to cause problems for companies that read data off the tags. They speculated that consumer activist groups could use smart tags viruses to cause havoc at stores they are targeting.
In some cases, said the researchers, viruses could be spread by household pets such as cats and dogs that are injected with the tags to help identify their owner.
The researchers urged companies working on RFID systems to start thinking seriously about security measures to protect against future threats.
(www.bbc.com - Wednesday, 15 March 2006, 18:02 GMT)
Wednesday, March 15, 2006
Build your own profiling tool by Andrew Wilcox
Create an ideal profiler using the Java 5 agent interface and AOP
Profiling is a technique for measuring where software programs consume resources, including CPU time and memory. In this article, software architect Andrew Wilcox explains the benefits of profiling and some current profiling options and their shortcomings. He then shows you how to use the new Java™ 5 agent interface and simple aspect-oriented programming techniques to build your own profiler.
Whether you're using System.out.println() or a profiling tool such as hprof or OptimizeIt, code profiling should be an essential component of your software development practice. This article discusses the most common approaches to code profiling and explains their downsides. It provides a list of best-of-breed features you might look for in an ideal profiler and explains why aspect-oriented techniques are well suited to achieving some of those features. It also introduces you to the JDK 5.0 agent interface and walks you through the steps of using it to build your own aspect-oriented profiler.
Note that the example profiler and complete source code for this article are based on the Java Interactive Profiler (JIP) -- an open-source profiler built using aspect-oriented techniques and the Java 5 agent interface. See Resources to learn more about JIP and other tools discussed in this article.
Profiling tools and techniques
Most Java developers start out measuring application performance using System.currentTimeMillis() and System.out.println(). System.currentTimeMillis() is easy to use: you just measure the time at the beginning of a method and again at the end, and print the difference, but it has two big downsides:
It's a manual process, requiring you to determine what code to measure; instrument the code; recompile, redeploy, run, and analyze the results; back out the instrumentation code when done; and go through all the same steps again the next time there's a problem.
It doesn't give a comprehensive view of how all the parts of the application are performing.
To get around these issues, some developers turn to code profilers like hprof, JProbe, or OptimizeIt. Profilers avoid the problems associated with ad-hoc measurement because you don't have to modify your program to use them. They also give you a more comprehensive view of program performance because they gather timing information for every method call, not just a particular section of the code. Unfortunately, profiling tools also have some downsides.
Limitations of profilers
Profilers offer a nice alternative to manual solutions like System.currentTimeMillis(), but they're far from ideal. For one thing, running a program with hprof can slow it down by a factor of 20. That means an ETL (extract, transform, and load) operation that normally takes an hour could take a full day to profile! Not only is waiting inconvenient, but changing the timescale of the application can actually skew the results. Take a program that does a lot of I/O. Because the I/O is performed by the operating system, the profiler doesn't slow it down, so your I/O could appear to run 20 times faster than it actually does! As a result, you can't always count on hprof to give you an accurate picture of your application's performance.
Another problem with hprof has to do with how Java programs are loaded and run. Unlike programs in statically linked languages like C or C++, a Java program is linked at run time rather than compile time. Classes aren't loaded by the JVM until the first time they're referenced, and code isn't compiled from bytecode to machine code until it has been executed a number of times. If you're trying to measure the performance of a method but its class hasn't yet been loaded, your measurement will include the class loading time and compilation time in addition to the run time. Because these things happen only at the beginning of an application's life, you usually don't want to include them when measuring the performance of long-lived applications.
Things can get even more complicated when your code is running in an application server or servlet engine. Profilers like hprof profile the entire application, servlet container and all. The trouble is, you usually don't want to profile the servlet engine, you just want to profile your application.
The ideal profiler
Like selecting any other tool, selecting a profiler involves trade-offs. Free tools like hprof are easy to use, but they have limitations, such as the inability to filter out classes or packages from the profile. Commercial tools offer more features but can be expensive and have restrictive licensing terms. Some profilers require that you launch the application through the profiler, which means reconstructing your execution environment in terms of an unfamiliar tool. Picking a profiler involves compromises, so what should an ideal profiler look like? Here's a short list of the features you might look for:
Speed: Profiling can be painfully slow. But you can speed things up by using a profiler that doesn't automatically profile every class.
Interactivity: The more interaction your profiler allows, the more you can fine-tune the information you get from it. For example, being able to turn the profiler on and off at run time helps you avoid measuring class loading, compilation, and interpreted execution (pre-JIT) times.
Filtering: Filtering by class or package lets you focus on the problem at hand, rather than being overwhelmed by too much information.
100% Pure Java code: Most profilers require native libraries, which limits the number of platforms that you can use them on. An ideal profiler wouldn't require the use of native libraries.
Open source: Open source tools typically let you get up and running quickly, while avoiding the restrictions of commercial licenses.
Build it yourself!
The problem with using System.currentTimeMillis() to generate timing information is that it's a manual process. If you could automate the instrumentation of the code, many of its disadvantages would go away. This type of problem is a perfect candidate for an aspect-oriented solution. The agent interface introduced in Java 5 is ideal for building an aspect-oriented profiler because it gives you an easy way to hook into the classloader and modify classes as they're loaded.
The remainder of the article focuses on the BYOP (build your own profiler). I'll introduce the agent interface and show you how to create a simple agent. You'll learn the code for a basic profiling aspect, as well as the steps you can take to modify it for more advanced profiling.
Creating an agent
The -javaagent JVM option is, unfortunately, very sparsely documented. You won't find many books on the topic (no Java Agents for Dummies or Java Agents in 21 days), but you will find some good sources in the Resources section, along with the overview here.
The basic idea behind agents is that, as the JVM loads a class, the agent can modify the class's bytecode. You can create an agent in three steps:
The basic idea behind agents is that, as the JVM loads a class, the agent can modify the class's bytecode. You can create an agent in three steps:
Implement the java.lang.instrument.ClassFileTransformer interface:
public interface ClassFileTransformer {
public byte[] transform(ClassLoader loader, String className,
Class classBeingRedefined, ProtectionDomain protectionDomain,
byte[] classfileBuffer) throws IllegalClassFormatException;
}
Create a "premain" method. This method is called before the application's main() method and looks like this:
package sample.verboseclass;
public class Main {
public static void premain(String args, Instrumentation inst) {
...
}
}
In the agent JAR file, include a manifest entry identifying the class containing the premain() method:
Manifest-Version: 1.0
Premain-Class: sample.verboseclass.Main
A simple agent
Your first step toward building a profiler is to create a simple agent that prints out the name of each class as it's loaded, similar to the behavior of the -verbose:class JVM option. As you can see in Listing 1, this requires only a few lines of code:
Listing 1. A simple agent
package sample.verboseclass;
public class Main {
public static void premain(String args, Instrumentation inst) {
inst.addTransformer(new Transformer());
}
}
class Transformer implements ClassFileTransformer {
public byte[] transform(ClassLoader l, String className, Class c,
ProtectionDomain pd, byte[] b) throws IllegalClassFormatException {
System.out.print("Loading class: ");
System.out.println(className);
return b;
}
}
If the agent was packaged in a JAR file called vc.jar, the JVM would be started with the -javaagent option, as follows:
java -javaagent:vc.jar MyApplicationClass
A profiling aspect
With the basic elements of an agent in place, your next step is to add a simple profiling aspect to your application classes as they're loaded. Fortunately, you don't need to master the details of the JVM instruction set to modify bytecode. Instead, you can use a toolkit like the ASM library (from the ObjectWeb consortium; see Resources) to handle the details of the class file format. ASM is a Java bytecode manipulation framework that uses the Visitor pattern to enable you to transform class files, in much the same way that SAX events can be used to traverse and transform an XML document.
Listing 2 is a profiling aspect that can be used to output the class name, method name, and a timestamp every time the JVM enters or leaves a method. (For a more sophisticated profiler, you would probably want to use a high-resolution timer like Java 5's System.nanoTime().)
Listing 2. A simple profiling aspect
package sample.profiler;
public class Profile {
public static void start(String className, String methodName) {
System.out.println(new StringBuilder(className)
.append('\t')
.append(methodName)
.append("\tstart\t")
.append(System.currentTimeMillis()));
}
public static void end(String className, String methodName) {
System.out.println(new StringBuilder(className)
.append('\t')
.append(methodName)
.append("\end\t")
.append(System.currentTimeMillis()));
}
}
If you were profiling by hand, your next step would be to modify every method to look something like this:
void myMethod() {
Profile.start("MyClass", "myMethod");
...
Profile.end("MyClass", "myMethod");
}
Using the ASM plugin
Now you need to figure out what the bytecode for the Profile.start() and Profile.end() calls looks like -- which is where the ASM library comes in. ASM has a Bytecode Outline plugin for Eclipse (see Resources) that allows you to view the bytecode of any class or method. Figure 1 shows the bytecode for the method above. (You could also use a dis-assembler like javap, which is part of the JDK.)
You can cut and paste the highlighted code shown in Figure 2 into your agent to call a generalized version of the Profile.start() method, as shown in Listing 3:
Listing 3. The ASM code to inject a call to the profiler
visitLdcInsn(className);
visitLdcInsn(methodName);
visitMethodInsn(INVOKESTATIC,
"sample/profiler/Profile",
"start",
"(Ljava/lang/String;Ljava/lang/String;)V");
To inject the start and end calls, subclass ASM's MethodAdapter, as shown in Listing 4:
Listing 4. The ASM code to inject a call to the profiler
package sample.profiler;
import org.objectweb.asm.MethodAdapter;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
import static org.objectweb.asm.Opcodes.INVOKESTATIC;
public class PerfMethodAdapter extends MethodAdapter {
private String className, methodName;
public PerfMethodAdapter(MethodVisitor visitor, String className,
String methodName) {
super(visitor);
className = className;
methodName = methodName;
}
public void visitCode() {
this.visitLdcInsn(className);
this.visitLdcInsn(methodName);
this.visitMethodInsn(INVOKESTATIC,
"sample/profiler/Profile",
"start",
"(Ljava/lang/String;Ljava/lang/String;)V");
super.visitCode();
}
public void visitInsn(int inst) {
switch (inst) {
case Opcodes.ARETURN:
case Opcodes.DRETURN:
case Opcodes.FRETURN:
case Opcodes.IRETURN:
case Opcodes.LRETURN:
case Opcodes.RETURN:
case Opcodes.ATHROW:
this.visitLdcInsn(className);
this.visitLdcInsn(methodName);
this.visitMethodInsn(INVOKESTATIC,
"sample/profiler/Profile",
"end",
"(Ljava/lang/String;Ljava/lang/String;)V");
break;
default:
break;
}
super.visitInsn(inst);
}
}
The code to hook this into your agent is very simple and is part of the source download for this article.
Loading the ASM classes
Because your agent uses ASM, you need to ensure that the ASM classes are loaded for everything to work. There are many class paths in a Java application: the application classpath, the extensions classpath, and the bootstrap classpath. Surprisingly, the ASM JAR doesn't go in any of these; instead, you'll use the manifest to tell the JVM which JAR files the agent needs, as shown in Listing 5. In this case, the JAR files must be in the same directory as the agent's JAR.
Listing 5. The manifest file for the profiler
Manifest-Version: 1.0
Premain-Class: sample.profiler.Main
Boot-Class-Path: asm-2.0.jar asm-attrs-2.0.jar asm-commons-2.0.jar
Running the profiler
Once everything is compiled and packaged, you can run your profiler against any Java application. Listing 6 is part of the output from a profile of Ant running the build.xml that compiles the agent:
Listing 6. A sample of the output from the profiler
org/apache/tools/ant/Main runBuild start 1138565072002
org/apache/tools/ant/Project start 1138565072029
org/apache/tools/ant/Project$AntRefTable start 1138565072031
org/apache/tools/ant/Project$AntRefTable end 1138565072033
org/apache/tools/ant/types/FilterSet start 1138565072054
org/apache/tools/ant/types/DataType start 1138565072055
org/apache/tools/ant/ProjectComponent start 1138565072055
org/apache/tools/ant/ProjectComponent end 1138565072055
org/apache/tools/ant/types/DataType end 1138565072055
org/apache/tools/ant/types/FilterSet end 1138565072055
org/apache/tools/ant/ProjectComponent setProject start 1138565072055
org/apache/tools/ant/ProjectComponent setProject end 1138565072055
org/apache/tools/ant/types/FilterSetCollection start 1138565072057
org/apache/tools/ant/types/FilterSetCollection addFilterSet start 1138565072057
org/apache/tools/ant/types/FilterSetCollection addFilterSet end 1138565072057
org/apache/tools/ant/types/FilterSetCollection end 1138565072057
org/apache/tools/ant/util/FileUtils start 1138565072075
org/apache/tools/ant/util/FileUtils end 1138565072076
org/apache/tools/ant/util/FileUtils newFileUtils start 1138565072076
org/apache/tools/ant/util/FileUtils start 1138565072076
org/apache/tools/ant/taskdefs/condition/Os start 1138565072080
org/apache/tools/ant/taskdefs/condition/Os end 1138565072081
org/apache/tools/ant/taskdefs/condition/Os isFamily start 1138565072082
org/apache/tools/ant/taskdefs/condition/Os isOs start 1138565072082
org/apache/tools/ant/taskdefs/condition/Os isOs end 1138565072082
org/apache/tools/ant/taskdefs/condition/Os isFamily end 1138565072082
org/apache/tools/ant/util/FileUtils end 1138565072082
org/apache/tools/ant/util/FileUtils newFileUtils end 1138565072082
org/apache/tools/ant/input/DefaultInputHandler start 1138565072084
org/apache/tools/ant/input/DefaultInputHandler end 1138565072085
org/apache/tools/ant/Project end 1138565072085
org/apache/tools/ant/Project setCoreLoader start 1138565072085
org/apache/tools/ant/Project setCoreLoader end 1138565072085
org/apache/tools/ant/Main addBuildListener start 1138565072085
org/apache/tools/ant/Main createLogger start 1138565072085
org/apache/tools/ant/DefaultLogger start 1138565072092
org/apache/tools/ant/util/StringUtils start 1138565072096
org/apache/tools/ant/util/StringUtils end 1138565072096
Tracking the call stack
So far you've seen how to build a simple aspect-oriented profiler with just a few lines of code. While a good start, the example profiler doesn't gather thread and call stack data. Call stack information is necessary to determine the gross and net method execution times. In addition, each call stack is associated with a thread, so if you want to track call stack data, you'll need thread information as well. Most profilers use a two-pass design for this kind of analysis: first gather data, then analyze it. I'll show you how to adopt this approach rather than just printing out the data as it is gathered.
Modifying the Profile class
You can easily enhance your Profile class to capture call stack and thread information. For starters, instead of printing out times at the start and end of each method, you can store the information using the data structures shown in Figure 3:
There are a number of ways to gather information about the call stack. One is to instantiate an Exception, but doing this at the beginning and end of each method would be far too slow. A simpler way is for the profiler to manage its own internal call stack. This is easy because start() is called for every method; the only tricky part is unwinding the internal call stack when an exception is thrown. You can detect when an exception has been thrown by checking the expected class and method name when Profile.end() is called.
Printing is similarly easy to set up. You can create a shutdown hook using Runtime.addShutdownHook() to register a Thread that runs at shutdown time and prints a profiling report to the console.
In conclusion
This article introduced you to the current tools and technologies most commonly used for profiling and discussed some of their limitations. You now have a list of features you might expect from an ideal profiler. Finally, you learned how to use aspect-oriented programming and the Java 5 agent interface to build your own profiler incorporating some of these ideal features.
The example code in this article is based on the Java Interactive Profiler, an open-source profiler built using the techniques I've discussed here. In addition to the basic features found in the example profiler, JIP incorporates the following:
Interactive profiling
The ability to exclude classes or packages
The ability to include only classes loaded by a particular classloader
A facility for tracking object allocations
Performance measurement in addition to code profiling
JIP is distributed under a BSD-style license. See Resources for download information.
(http://www-128.ibm.com/developerworks/java/library/j-jip/index.html?ca=drs-#download)
Profiling is a technique for measuring where software programs consume resources, including CPU time and memory. In this article, software architect Andrew Wilcox explains the benefits of profiling and some current profiling options and their shortcomings. He then shows you how to use the new Java™ 5 agent interface and simple aspect-oriented programming techniques to build your own profiler.
Whether you're using System.out.println() or a profiling tool such as hprof or OptimizeIt, code profiling should be an essential component of your software development practice. This article discusses the most common approaches to code profiling and explains their downsides. It provides a list of best-of-breed features you might look for in an ideal profiler and explains why aspect-oriented techniques are well suited to achieving some of those features. It also introduces you to the JDK 5.0 agent interface and walks you through the steps of using it to build your own aspect-oriented profiler.
Note that the example profiler and complete source code for this article are based on the Java Interactive Profiler (JIP) -- an open-source profiler built using aspect-oriented techniques and the Java 5 agent interface. See Resources to learn more about JIP and other tools discussed in this article.
Profiling tools and techniques
Most Java developers start out measuring application performance using System.currentTimeMillis() and System.out.println(). System.currentTimeMillis() is easy to use: you just measure the time at the beginning of a method and again at the end, and print the difference, but it has two big downsides:
It's a manual process, requiring you to determine what code to measure; instrument the code; recompile, redeploy, run, and analyze the results; back out the instrumentation code when done; and go through all the same steps again the next time there's a problem.
It doesn't give a comprehensive view of how all the parts of the application are performing.
To get around these issues, some developers turn to code profilers like hprof, JProbe, or OptimizeIt. Profilers avoid the problems associated with ad-hoc measurement because you don't have to modify your program to use them. They also give you a more comprehensive view of program performance because they gather timing information for every method call, not just a particular section of the code. Unfortunately, profiling tools also have some downsides.
Limitations of profilers
Profilers offer a nice alternative to manual solutions like System.currentTimeMillis(), but they're far from ideal. For one thing, running a program with hprof can slow it down by a factor of 20. That means an ETL (extract, transform, and load) operation that normally takes an hour could take a full day to profile! Not only is waiting inconvenient, but changing the timescale of the application can actually skew the results. Take a program that does a lot of I/O. Because the I/O is performed by the operating system, the profiler doesn't slow it down, so your I/O could appear to run 20 times faster than it actually does! As a result, you can't always count on hprof to give you an accurate picture of your application's performance.
Another problem with hprof has to do with how Java programs are loaded and run. Unlike programs in statically linked languages like C or C++, a Java program is linked at run time rather than compile time. Classes aren't loaded by the JVM until the first time they're referenced, and code isn't compiled from bytecode to machine code until it has been executed a number of times. If you're trying to measure the performance of a method but its class hasn't yet been loaded, your measurement will include the class loading time and compilation time in addition to the run time. Because these things happen only at the beginning of an application's life, you usually don't want to include them when measuring the performance of long-lived applications.
Things can get even more complicated when your code is running in an application server or servlet engine. Profilers like hprof profile the entire application, servlet container and all. The trouble is, you usually don't want to profile the servlet engine, you just want to profile your application.
The ideal profiler
Like selecting any other tool, selecting a profiler involves trade-offs. Free tools like hprof are easy to use, but they have limitations, such as the inability to filter out classes or packages from the profile. Commercial tools offer more features but can be expensive and have restrictive licensing terms. Some profilers require that you launch the application through the profiler, which means reconstructing your execution environment in terms of an unfamiliar tool. Picking a profiler involves compromises, so what should an ideal profiler look like? Here's a short list of the features you might look for:
Speed: Profiling can be painfully slow. But you can speed things up by using a profiler that doesn't automatically profile every class.
Interactivity: The more interaction your profiler allows, the more you can fine-tune the information you get from it. For example, being able to turn the profiler on and off at run time helps you avoid measuring class loading, compilation, and interpreted execution (pre-JIT) times.
Filtering: Filtering by class or package lets you focus on the problem at hand, rather than being overwhelmed by too much information.
100% Pure Java code: Most profilers require native libraries, which limits the number of platforms that you can use them on. An ideal profiler wouldn't require the use of native libraries.
Open source: Open source tools typically let you get up and running quickly, while avoiding the restrictions of commercial licenses.
Build it yourself!
The problem with using System.currentTimeMillis() to generate timing information is that it's a manual process. If you could automate the instrumentation of the code, many of its disadvantages would go away. This type of problem is a perfect candidate for an aspect-oriented solution. The agent interface introduced in Java 5 is ideal for building an aspect-oriented profiler because it gives you an easy way to hook into the classloader and modify classes as they're loaded.
The remainder of the article focuses on the BYOP (build your own profiler). I'll introduce the agent interface and show you how to create a simple agent. You'll learn the code for a basic profiling aspect, as well as the steps you can take to modify it for more advanced profiling.
Creating an agent
The -javaagent JVM option is, unfortunately, very sparsely documented. You won't find many books on the topic (no Java Agents for Dummies or Java Agents in 21 days), but you will find some good sources in the Resources section, along with the overview here.
The basic idea behind agents is that, as the JVM loads a class, the agent can modify the class's bytecode. You can create an agent in three steps:
The basic idea behind agents is that, as the JVM loads a class, the agent can modify the class's bytecode. You can create an agent in three steps:
Implement the java.lang.instrument.ClassFileTransformer interface:
public interface ClassFileTransformer {
public byte[] transform(ClassLoader loader, String className,
Class classBeingRedefined, ProtectionDomain protectionDomain,
byte[] classfileBuffer) throws IllegalClassFormatException;
}
Create a "premain" method. This method is called before the application's main() method and looks like this:
package sample.verboseclass;
public class Main {
public static void premain(String args, Instrumentation inst) {
...
}
}
In the agent JAR file, include a manifest entry identifying the class containing the premain() method:
Manifest-Version: 1.0
Premain-Class: sample.verboseclass.Main
A simple agent
Your first step toward building a profiler is to create a simple agent that prints out the name of each class as it's loaded, similar to the behavior of the -verbose:class JVM option. As you can see in Listing 1, this requires only a few lines of code:
Listing 1. A simple agent
package sample.verboseclass;
public class Main {
public static void premain(String args, Instrumentation inst) {
inst.addTransformer(new Transformer());
}
}
class Transformer implements ClassFileTransformer {
public byte[] transform(ClassLoader l, String className, Class c,
ProtectionDomain pd, byte[] b) throws IllegalClassFormatException {
System.out.print("Loading class: ");
System.out.println(className);
return b;
}
}
If the agent was packaged in a JAR file called vc.jar, the JVM would be started with the -javaagent option, as follows:
java -javaagent:vc.jar MyApplicationClass
A profiling aspect
With the basic elements of an agent in place, your next step is to add a simple profiling aspect to your application classes as they're loaded. Fortunately, you don't need to master the details of the JVM instruction set to modify bytecode. Instead, you can use a toolkit like the ASM library (from the ObjectWeb consortium; see Resources) to handle the details of the class file format. ASM is a Java bytecode manipulation framework that uses the Visitor pattern to enable you to transform class files, in much the same way that SAX events can be used to traverse and transform an XML document.
Listing 2 is a profiling aspect that can be used to output the class name, method name, and a timestamp every time the JVM enters or leaves a method. (For a more sophisticated profiler, you would probably want to use a high-resolution timer like Java 5's System.nanoTime().)
Listing 2. A simple profiling aspect
package sample.profiler;
public class Profile {
public static void start(String className, String methodName) {
System.out.println(new StringBuilder(className)
.append('\t')
.append(methodName)
.append("\tstart\t")
.append(System.currentTimeMillis()));
}
public static void end(String className, String methodName) {
System.out.println(new StringBuilder(className)
.append('\t')
.append(methodName)
.append("\end\t")
.append(System.currentTimeMillis()));
}
}
If you were profiling by hand, your next step would be to modify every method to look something like this:
void myMethod() {
Profile.start("MyClass", "myMethod");
...
Profile.end("MyClass", "myMethod");
}
Using the ASM plugin
Now you need to figure out what the bytecode for the Profile.start() and Profile.end() calls looks like -- which is where the ASM library comes in. ASM has a Bytecode Outline plugin for Eclipse (see Resources) that allows you to view the bytecode of any class or method. Figure 1 shows the bytecode for the method above. (You could also use a dis-assembler like javap, which is part of the JDK.)
You can cut and paste the highlighted code shown in Figure 2 into your agent to call a generalized version of the Profile.start() method, as shown in Listing 3:
Listing 3. The ASM code to inject a call to the profiler
visitLdcInsn(className);
visitLdcInsn(methodName);
visitMethodInsn(INVOKESTATIC,
"sample/profiler/Profile",
"start",
"(Ljava/lang/String;Ljava/lang/String;)V");
To inject the start and end calls, subclass ASM's MethodAdapter, as shown in Listing 4:
Listing 4. The ASM code to inject a call to the profiler
package sample.profiler;
import org.objectweb.asm.MethodAdapter;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
import static org.objectweb.asm.Opcodes.INVOKESTATIC;
public class PerfMethodAdapter extends MethodAdapter {
private String className, methodName;
public PerfMethodAdapter(MethodVisitor visitor, String className,
String methodName) {
super(visitor);
className = className;
methodName = methodName;
}
public void visitCode() {
this.visitLdcInsn(className);
this.visitLdcInsn(methodName);
this.visitMethodInsn(INVOKESTATIC,
"sample/profiler/Profile",
"start",
"(Ljava/lang/String;Ljava/lang/String;)V");
super.visitCode();
}
public void visitInsn(int inst) {
switch (inst) {
case Opcodes.ARETURN:
case Opcodes.DRETURN:
case Opcodes.FRETURN:
case Opcodes.IRETURN:
case Opcodes.LRETURN:
case Opcodes.RETURN:
case Opcodes.ATHROW:
this.visitLdcInsn(className);
this.visitLdcInsn(methodName);
this.visitMethodInsn(INVOKESTATIC,
"sample/profiler/Profile",
"end",
"(Ljava/lang/String;Ljava/lang/String;)V");
break;
default:
break;
}
super.visitInsn(inst);
}
}
The code to hook this into your agent is very simple and is part of the source download for this article.
Loading the ASM classes
Because your agent uses ASM, you need to ensure that the ASM classes are loaded for everything to work. There are many class paths in a Java application: the application classpath, the extensions classpath, and the bootstrap classpath. Surprisingly, the ASM JAR doesn't go in any of these; instead, you'll use the manifest to tell the JVM which JAR files the agent needs, as shown in Listing 5. In this case, the JAR files must be in the same directory as the agent's JAR.
Listing 5. The manifest file for the profiler
Manifest-Version: 1.0
Premain-Class: sample.profiler.Main
Boot-Class-Path: asm-2.0.jar asm-attrs-2.0.jar asm-commons-2.0.jar
Running the profiler
Once everything is compiled and packaged, you can run your profiler against any Java application. Listing 6 is part of the output from a profile of Ant running the build.xml that compiles the agent:
Listing 6. A sample of the output from the profiler
org/apache/tools/ant/Main runBuild start 1138565072002
org/apache/tools/ant/Project
org/apache/tools/ant/Project$AntRefTable
org/apache/tools/ant/Project$AntRefTable
org/apache/tools/ant/types/FilterSet
org/apache/tools/ant/types/DataType
org/apache/tools/ant/ProjectComponent
org/apache/tools/ant/ProjectComponent
org/apache/tools/ant/types/DataType
org/apache/tools/ant/types/FilterSet
org/apache/tools/ant/ProjectComponent setProject start 1138565072055
org/apache/tools/ant/ProjectComponent setProject end 1138565072055
org/apache/tools/ant/types/FilterSetCollection
org/apache/tools/ant/types/FilterSetCollection addFilterSet start 1138565072057
org/apache/tools/ant/types/FilterSetCollection addFilterSet end 1138565072057
org/apache/tools/ant/types/FilterSetCollection
org/apache/tools/ant/util/FileUtils
org/apache/tools/ant/util/FileUtils
org/apache/tools/ant/util/FileUtils newFileUtils start 1138565072076
org/apache/tools/ant/util/FileUtils
org/apache/tools/ant/taskdefs/condition/Os
org/apache/tools/ant/taskdefs/condition/Os
org/apache/tools/ant/taskdefs/condition/Os isFamily start 1138565072082
org/apache/tools/ant/taskdefs/condition/Os isOs start 1138565072082
org/apache/tools/ant/taskdefs/condition/Os isOs end 1138565072082
org/apache/tools/ant/taskdefs/condition/Os isFamily end 1138565072082
org/apache/tools/ant/util/FileUtils
org/apache/tools/ant/util/FileUtils newFileUtils end 1138565072082
org/apache/tools/ant/input/DefaultInputHandler
org/apache/tools/ant/input/DefaultInputHandler
org/apache/tools/ant/Project
org/apache/tools/ant/Project setCoreLoader start 1138565072085
org/apache/tools/ant/Project setCoreLoader end 1138565072085
org/apache/tools/ant/Main addBuildListener start 1138565072085
org/apache/tools/ant/Main createLogger start 1138565072085
org/apache/tools/ant/DefaultLogger
org/apache/tools/ant/util/StringUtils
org/apache/tools/ant/util/StringUtils
Tracking the call stack
So far you've seen how to build a simple aspect-oriented profiler with just a few lines of code. While a good start, the example profiler doesn't gather thread and call stack data. Call stack information is necessary to determine the gross and net method execution times. In addition, each call stack is associated with a thread, so if you want to track call stack data, you'll need thread information as well. Most profilers use a two-pass design for this kind of analysis: first gather data, then analyze it. I'll show you how to adopt this approach rather than just printing out the data as it is gathered.
Modifying the Profile class
You can easily enhance your Profile class to capture call stack and thread information. For starters, instead of printing out times at the start and end of each method, you can store the information using the data structures shown in Figure 3:
There are a number of ways to gather information about the call stack. One is to instantiate an Exception, but doing this at the beginning and end of each method would be far too slow. A simpler way is for the profiler to manage its own internal call stack. This is easy because start() is called for every method; the only tricky part is unwinding the internal call stack when an exception is thrown. You can detect when an exception has been thrown by checking the expected class and method name when Profile.end() is called.
Printing is similarly easy to set up. You can create a shutdown hook using Runtime.addShutdownHook() to register a Thread that runs at shutdown time and prints a profiling report to the console.
In conclusion
This article introduced you to the current tools and technologies most commonly used for profiling and discussed some of their limitations. You now have a list of features you might expect from an ideal profiler. Finally, you learned how to use aspect-oriented programming and the Java 5 agent interface to build your own profiler incorporating some of these ideal features.
The example code in this article is based on the Java Interactive Profiler, an open-source profiler built using the techniques I've discussed here. In addition to the basic features found in the example profiler, JIP incorporates the following:
Interactive profiling
The ability to exclude classes or packages
The ability to include only classes loaded by a particular classloader
A facility for tracking object allocations
Performance measurement in addition to code profiling
JIP is distributed under a BSD-style license. See Resources for download information.
(http://www-128.ibm.com/developerworks/java/library/j-jip/index.html?ca=drs-#download)
How did I miss this? java.util.Collections
Well, they say you learn something new everyday. And given the size of the Java API, thats not too hard to believe.
After doing serious Java programming for at a least a few years, and having dabbled for a few years more (all the way back to the 1.0 days!), I’m pretty happy with my breadth of Java knowledge. Until a co-worker today mentioned using Collections.shuffle() to randomize a list.
“Pffffft”, says I, “Surely you jest”, says I. “No such thing.”
Well, there is. java.util.Collections (not Collection, note - theres an “s” on the end!). A nice, chunky class, full of juicy, static methods just waiting to save you from having to re-invent the wheel when it comes to operating on Collections. There’s the obvious stuff - shuffle() and sort() to randomize and sort, for instance. And small, but useful stuff - min() and max(), swap(). And some real useful stuff, like synchronizedList() (which returns a thread safe version of your list).
Many’s the time I’ve done my own “max()” routine. Each time, I trawled through the Collection interface looking for one and was mildly surprised it didn’t exist. And I never thought to look any further afield. I’m guessing that there may be one or two Java guys out there who are in the same boat (How many library classes are there now in Java?). Seeing as my co-worker doesn’t have his own blog…yet (come on H! Get your act together!), I’m doing this posting for the other people like me!
Of course, I’ve always got the excuse for my ignorance that its a relatively recent addition. I mean, its only been around since Java 1.2…..
Another good one along those lines is java.util.Arrays.
(http://blogs.asman-it.com.au/dasman/index.php/20060313/how-did-i-miss-this-javautilcollections)
After doing serious Java programming for at a least a few years, and having dabbled for a few years more (all the way back to the 1.0 days!), I’m pretty happy with my breadth of Java knowledge. Until a co-worker today mentioned using Collections.shuffle() to randomize a list.
“Pffffft”, says I, “Surely you jest”, says I. “No such thing.”
Well, there is. java.util.Collections (not Collection, note - theres an “s” on the end!). A nice, chunky class, full of juicy, static methods just waiting to save you from having to re-invent the wheel when it comes to operating on Collections. There’s the obvious stuff - shuffle() and sort() to randomize and sort, for instance. And small, but useful stuff - min() and max(), swap(). And some real useful stuff, like synchronizedList() (which returns a thread safe version of your list).
Many’s the time I’ve done my own “max()” routine. Each time, I trawled through the Collection interface looking for one and was mildly surprised it didn’t exist. And I never thought to look any further afield. I’m guessing that there may be one or two Java guys out there who are in the same boat (How many library classes are there now in Java?). Seeing as my co-worker doesn’t have his own blog…yet (come on H! Get your act together!), I’m doing this posting for the other people like me!
Of course, I’ve always got the excuse for my ignorance that its a relatively recent addition. I mean, its only been around since Java 1.2…..
Another good one along those lines is java.util.Arrays.
(http://blogs.asman-it.com.au/dasman/index.php/20060313/how-did-i-miss-this-javautilcollections)
Thursday, March 09, 2006
Photos as Passwords Foil Hackers by Tracy Staedter
March 7, 2006— A password that uses images instead of numbers could give some people access to secure information on personal electronic devices or at ATMs within the next year.
The image authentication system uses a pair of digital images instead of a string of numbers to make logging in simple for the legitimate user, but difficult for impersonators.
"It is expected that many of the conventional user authentication systems would be able to be replaced with our scheme, since recognition of images is significantly easier for human beings than precise recall of passwords," said team leader Masakatsu Nishigaki, a professor of informatics at Shizuoka University in Japan, where the system is being developed.
According to Nishigaki, people often use four-digit number passwords or easy-to-remember passwords, such as a name or birthday, to access information on cell phones, PDAs, Web sites, and financial accounts at ATMs.
What's more, they often use the same password to gain access to several different location and rarely do they change the secret string of numbers.
That makes an otherwise secure system vulnerable to password cracking programs, which are designed to retrieve lost passwords but are also used by thieves to gain unauthorized access to accounts.
Nishigaki and his team propose a system that uses one clear and easily recognizable image and another that is a highly pixilated, unclear version of the original.
When creating a new password or changing an old one, the system provides the legitimate user with the clear image. But during the authentication phase, the system shows the user the unclear image, along with a number of decoy images.
To the user who holds the clear version, the unclear image is easy to pick out. But to an impersonator, finding the correct image becomes difficult.
Depending on the security level and to avoid an unauthorized person from clicking on the correct image by chance, the system can be designed to display a higher number of decoy images or to present the user with more than one round of image selection.
That security measure could also be a flaw in the unclear image system, said Tetsuji Takada, a researcher at the National Institute of Advanced Industrial Science and Technology in Tokyo whose team is also working on a photo-based authentication system.
"The solution significantly decreases the memorability of pass-images," said Takada. "There is a problem getting a better balance between security and usability in user authentication."
Takada's solution is to allow users to use their own photos, which would increase the chances that they would remember it. That photo is displayed among other decoy images in a group randomly selected by the computer.
For added security, the computer may display a group of photos that does not contain the pass-image. In that case, the user can answer "no pass-image."
An unauthorized person might continue to guess at the correct photo and give himself away.
Both groups are working toward an effective system. Takada's team will present new research findings at a conference this May.
Nishigaki's team recently filed for a patent and has been approached by at least one Japanese company that has expressed an interest in applying the system to their product.
(http://www.discovery.com/)
The image authentication system uses a pair of digital images instead of a string of numbers to make logging in simple for the legitimate user, but difficult for impersonators.
"It is expected that many of the conventional user authentication systems would be able to be replaced with our scheme, since recognition of images is significantly easier for human beings than precise recall of passwords," said team leader Masakatsu Nishigaki, a professor of informatics at Shizuoka University in Japan, where the system is being developed.
According to Nishigaki, people often use four-digit number passwords or easy-to-remember passwords, such as a name or birthday, to access information on cell phones, PDAs, Web sites, and financial accounts at ATMs.
What's more, they often use the same password to gain access to several different location and rarely do they change the secret string of numbers.
That makes an otherwise secure system vulnerable to password cracking programs, which are designed to retrieve lost passwords but are also used by thieves to gain unauthorized access to accounts.
Nishigaki and his team propose a system that uses one clear and easily recognizable image and another that is a highly pixilated, unclear version of the original.
When creating a new password or changing an old one, the system provides the legitimate user with the clear image. But during the authentication phase, the system shows the user the unclear image, along with a number of decoy images.
To the user who holds the clear version, the unclear image is easy to pick out. But to an impersonator, finding the correct image becomes difficult.
Depending on the security level and to avoid an unauthorized person from clicking on the correct image by chance, the system can be designed to display a higher number of decoy images or to present the user with more than one round of image selection.
That security measure could also be a flaw in the unclear image system, said Tetsuji Takada, a researcher at the National Institute of Advanced Industrial Science and Technology in Tokyo whose team is also working on a photo-based authentication system.
"The solution significantly decreases the memorability of pass-images," said Takada. "There is a problem getting a better balance between security and usability in user authentication."
Takada's solution is to allow users to use their own photos, which would increase the chances that they would remember it. That photo is displayed among other decoy images in a group randomly selected by the computer.
For added security, the computer may display a group of photos that does not contain the pass-image. In that case, the user can answer "no pass-image."
An unauthorized person might continue to guess at the correct photo and give himself away.
Both groups are working toward an effective system. Takada's team will present new research findings at a conference this May.
Nishigaki's team recently filed for a patent and has been approached by at least one Japanese company that has expressed an interest in applying the system to their product.
(http://www.discovery.com/)
Tuesday, March 07, 2006
LinkedList vs. ArrayList Published by Avah (January 19th, 2006)
On JavaKoans I was asked whether for a dynamic set of numbers one could use ArrayList. This brings up a good question: The Java Collections Framework offers a lot of implementions to its many interfaces. Sometimes its unclear when to use what.
I will try to supply an answer for the LinkedList / ArrayList issue. The first thing to do is to look at what interfaces these two implement. This might hint us at their purpose, as Sun usually bound purposes into interfaces.
// lang java
public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, Serializable
public class LinkedList
extends AbstractSequentialList
implements List, Queue
We can ignore Cloneable and Serializable as all of the JCF implement those. It’s also quite obvious that both of them implement the List interface, as they need to provide list functionability (backwards iteration, sub listing, etc).
Now for the differences: ArrayList is implementing RandomAccess while LinkedList implementing Queue. You could already tell something about the usage of the two classes.
ArrayList
Now for some implementation notes. The ArrayList is actually encapsulating an actualy Array, an Object[]. When you instanciate ArrayList, an array is created, and when you add values into it, the array changes its size accordingly. This gives you strengths and weaknesses:
- Fast Random Access You can perform random access without fearing for performence. Calling
- Adding values might be slow When you don’t know the amount of values the array will contain when you create it, a lot of shifting is going to be done in the memory space when the ArrayList manipulates its internal array.
- Slow manipulation When you’ll want to add a value randomly inside the array, between two already existing values, the array will have to start moving all the values one spot to the right in order to let that happen.
get(int) will just access the underlying array. LinkedList
The LinkedList is implemented using nodes linked to each other. Each node contains a previous node link, next node link, and value, which contains the actual data. When new data is inserted, a node is inserted and the links of the surrounding nodes are updated accordingly. When one is removed, the same happens - The surrounding nodes are changing their links and the deleted node is garbage collected. This, as well, gives strengths and weaknesses:
- Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantanious. Change two links, and you have a new value anywhere you want it.
- No random access Even though the
get(int)is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.
Some Conclusions
ArrayList is very useful when a well defined set of data is needed in a List interface as opposed to an array. It can be dynamically changed, but try not to do so frequently throughout the life of the application. LinkedList is there for you to do just that: Manipulating it is very easy, and as long as its used for iteration purposes only and not for random accessing, it’s the best solution. Further, if you need random accessing from time to time, I suggest toArray for that specific moment.
Another point I didn’t raise here is the Queue issue. LinkedList implements extended abilities to the normal List interface which allows it to add and remove elements from its beginning and end. This makes the LinkedList perfect for Queue and Stack purposes - Although in Java 5 they already added a Stack class.
Hope this helped someone. Tell me if you want to differ.
(http://javachaos.crazyredpanda.com/?p=99)
Subscribe to:
Posts (Atom)