Testing various Regular Expression solutions, Part 1

Edit: Please check also Part 1.5 for some further analysis.

For AdKiller to work properly, Regular expression matching should be supported. There are various RegExp solutions for the iPhoneOS:

1. regex.h
2. ICU's regular expression engine
3. PCRE
4. RegexKitLite, which is an ObjC wrapper of the ICU engine.
5. JavaScriptCore's regular expression engine.
6. Do it yourself!

For Ad blocking, we only need to test if the Regular Expression matches, so I've limited the test case to a simple RegExp.test only.

In this part, I'll test for the AdBlockPlus "wildcard rules", where a * matches anything, and optional | at the beginning or end to indicate an anchor. Because of the simplicity, we can actually do the test without using RegExp (e.g. using CFStringFind).

From the complexity of the RegExp engines, we would expect the time taken follow this order:

CFStringFind << regex.h << JSRegExp < ICU < RegexKitLite < PCRE

But somewhat surprisingly, the actual time taken is like this:

ICU       PCRE      regex.h   RKLite    JSRegExp  CFStrFind
-----------------------------------------------------------
0.253456s 0.069918s 1.726371s 1.651787s 0.139437s 0.078097s
0.275680s 0.067150s 1.715131s 1.652074s 0.112813s 0.075818s
0.251526s 0.067994s 1.716483s 1.637005s 0.113267s 0.075716s
0.250806s 0.067551s 1.721203s 1.626927s 0.113274s 0.075726s
0.251498s 0.067168s 1.716587s 1.651783s 0.113605s 0.076064s

So the ordering would be:

PCRE < CFStringFind < JSRegExp < ICU << RegexKitLite < regex.h

The most complex engine is the fastest! CFStringFind ranks the second probably because my code is not optimized, but this shows the PCRE engine is really efficient. JSRegExp was originally a PCRE with everything irrelevant to Javascript stripped out, but that is slower than PCRE by 2 times. The WebKit devs should think of what's wrong. RegexKitLite's performance is pretty disappointing. Although it is advertised as very efficient, it is still 6~7 times slower than bare-bone ICU. The problem is probably directly using NSString as the RegExp holder, instead of a dedicated RegExp class. And regex.h's result is really a *WTF*.

Edit: I have redone the test to eliminate some inconsistency (case sensitivity) and convert the regex.h's syntax form BRE to ERE. The result is impressive: ERE is faster than BRE by 7 fold, make in in par with ICU. The new results are:

Methods
ICU       PCRE      regex.h   RKLite    JSRegExp  CFStrFind
-----------------------------------------------------------
0.253736s 0.069918s 0.238111s 1.651787s 0.139437s 0.070956s
0.254308s 0.067150s 0.235963s 1.652074s 0.112813s 0.068302s
0.252483s 0.067994s 0.235714s 1.637005s 0.113267s 0.068710s
0.251647s 0.067551s 0.234380s 1.626927s 0.113274s 0.068353s
0.253102s 0.067168s 0.235367s 1.651783s 0.113605s 0.068280s

and the new ordering is:

PCRE ≈ CFStringFind < JSRegExp < regex.h < ICU << RegexKitLite

So PCRE is still the fastest, but with a smaller margin. And RegexKitLite is now win the title of the slowest RegEx implementation.

To conclude this part, we should use PCRE for wildcard testing, if speed and clarity are important.

The source code of the test can be found in http://pastie.org/495990. Basically, 323 URLs collected from 3 different sources are matched against 16 wildcard rules. The file is compiled with:
/Developer/Platforms/iPhoneOS.platform/Developer/usr/bin/gcc-4.0 -arch armv6 -std=c99 -isysroot /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS2.2.1.sdk -I/Developer/Platforms/iPhoneOS.platform/Developer/usr/include/gcc/darwin/default -I/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS2.2.1.sdk/usr/lib/gcc/arm-apple-darwin9/4.0.1/include -L/usr/local/lib -Wall -mcpu=arm1176jzf-s -O2 -L. -framework CoreFoundation -framework Foundation -licucore -lpcre main.m RegexKitLite.m ; ldid -S a.out
and run on a jailbroken iPod Touch 1G, firmware version 2.2.1.

Introducing Ad Killer

This is a short MS extension I've coded up as a direct respond to Greystripe's intrusive advertisement. (How intrusive it is? Download CubesFree and you'll know. C'mon, why not use AdMob?)

Ad Killer is a simple extension that hooks on the NSURLConnection class. It checks the URL against known criteria, and if it is determined as an Ad (or a bad site, whatever), it will convert the URL to a bad site that will always fail the request.

Unlike methods using .hosts, Ad Killer has the potential to support Regular Expressions, and thus AdBlock Plus filters (except element blocking). And unlike AdBlock by CocoaMug, it can work with almost all applications* (not just MobileSafari) and it is free.

Currently Ad Killer is not packaged for release, but you can check out the code at http://code.google.com/p/networkpx/source/browse/trunk/hk.kennytm.adkiller.

*: AdKiller will not work on Cydia, or any setuid apps that does not support MobileSubstrate.

An application that SpringBoard is not tracking just launched with identifier ... and will be killed.

If you directly run a UIKit app from command line, nothing will be shown, and the syslog will print:

An application that SpringBoard is not tracking just launched with identifier com.yourcompany.Untitled and will be killed.

Why? If you disassemble SpringBoard with thumb-ddis, you can quickly found this string is referred in the function 0x123ba. This function is called only from -[SpringBoard applicationStarted:], decompiled as:

@implementation SpringBoard
-(void)applicationStarted:(GSEventRef)event { _123ba(event); }
@end

So it is pretty easy to get the signature and purpose of this function. 0x123ba decompiled is roughly like:

void LaunchApplication (GSEventRef event) {
 GSEventRecord* pRecord = _GSEventGetGSEventRecord(event);

 struct GSEventAppLaunch {
  pid_t       pid;   // 48
  void*       m_52;   // 52
  const char  displayIdentifier[]; // 56
 }* pAppRecord = pRecord + 1;

 if (getpid() != pAppRecord->pid) {
  // call 11fc8
  NSString* displayIdentifier = NSStringCreateWithUTF8String(pAppRecord->displayIdentifier, pRecord->size - 8);
  if (displayIdentifier != nil) {
   // call 107d8
   SBApplication* app = SBApplicationGetWithDisplayIdentifier(displayIdentifier);
   // 123e8
   if (app != nil) {
    [app sendActivationEvent:event];
    [displayIdentifier release];
    return;
   }
  }
  // 123fa
  NSLog(@"An application that SpringBoard is not tracking just launched with identifier %@ and will be killed.", displayIdentifier);
  kill(pAppRecord->pid, 9);
  [displayIdentifier release];
 }
}

Since we are getting prompt of the display ID there is no reason the condition displayIdentifier != nil will fail, so it must be due to app == nil. We can set a break point at 0x123e8, and indeed, it returns nil. But having the same argument, why one returns a valid object and one returns nil? There must be some global variables it relies on. Let's take a look at 0x107d8 to be sure.

The function 0x107d8 roughly translates to:

SBApplication* SBApplicationGetWithDisplayIdentifier(NSString* identifier) { return _106a0(DisplayStack_e7004, identifier) ?: _106a0(DisplayStack_e7014, identifier) ?: _106a0(DisplayStack_e7008, identifier); }

The DisplayStack_xxx are instances of SBDisplayStack. In this context, SBDisplayStack is like an array of SBApplication, and the function 0x106a0 merely search for an SBApplication having the specified identifier from the stack. So what we are checking is already an aftereffect.

(more about Display stack: http://code.google.com/p/iphone-tweaks/wiki/DevelopmentNotes)

Just for fun: Some undocumented flags of ldid

ldid was used most commonly to pseudosign an app, so that it would run in a jailbroken device. It is also used to attach an entitlement file to an executable. But besides the well-known -S (pseudosign/add entitlement) and less-well-known -e (dump entitlement) flag, there are a couple of flags went undocumented.

-p <Files>	Print the paths of the input files.
-u <Files>	Print the UUID of the input files.
-t <Files>	Print the timestamp of a dylib.
-T<NewTimestamp> <Files>	Assign the timestamp of a dylib. Pass "-" to <NewTimestamp> to assign the timestamp to a hash.
-s	Calculate the sha1 without changing anything. Incompatible with the -S flag.

Experiment: An alternative way to extract hidden symbols

A library usually have symbols defined functions and variables to allow external code access its functions, or help debugging. There are external (public) and hidden symbols. The external symbols can be picked up by dyld to broadcast the correct place of the functions. The hidden ones will be ignored, however, for performance reasons, or just to hide some interesting calls.

And the hidden ones are often interesting. For example, WinterBoard needed 7 hidden symbols to work.

Fortunately, the address each symbol points to, hidden or not, is defined alongside the library, so one can read the library file to get all the symbols.

In fact, Apple provided the nlist function for this purpose. But nlist is sloooooow. So slow that saurik has improved the backend of nlist the next version of MobileSubstrate (which delivered more than 10 times speed improvement.)

But how did I step in this? Originally I tried to create a transition filter for QuartzCore. This requires me to access the C++ backend of the QC, which are all hidden symbols. So I use nlist as usual. And I've written a wrapper function using va_arg to make it simpler to use. Then it crashed. Why? There's one caveat — on x86 the QuartzCore is slided. The address returned from nlist — which is just being read statically — is invalid because a run-time offset must be added to it.

This slide can be obtained using the dyld function _dyld_get_image_vmaddr_slide. But it takes an integer! What integer? This is an index of all images loaded by dyld. To check which image it is pointed to, one needs to call _dyld_get_image_name. That's troublesome, and adds extra slowness to the nlist method.

But there's also a _dyld_get_image_header function. This function returns the Mach-O header, which can guide you to do the same thing nlist does, but on the loaded image. Because it is loaded, every read/write will be on the RAM, and it will be much faster than file access. That's good! Except it crashed again — the loaded image is not a direct copy-and-paste. Some part (the __DATA, __OBJC and __IMPORT segments, to be precise) are skipped from the object file. And the same solution for treating QuartzCore cannot be used on UIKit.

So I started to dig the source code of dyld, which I found that these 3 APIs are just C wrapper to a various (i.e. hidden) C++ function. The function, dyld::getIndexedImage, returns a class pointer that has everything I need. Everything. It has the symbol table, the strings table, and the Mach-O header, and that's enough for exploring hidden symbols.

Of course, since dyld::getIndexedImage is hidden, to call it we need to nlist it too... Or not. saurik has already shown that rewriting nlist improves the speed by 10x, why not do it here also? The result, therefore, is this monster:

http://pastie.org/485348.

It has been tested and works on ARM and i386. Experimentally, running the main() function gives the timing in 5 runs:

nlist	lookup_function_pointers
0.517996s	0.026339s
0.498724s	0.013721s
0.498352s	0.013623s
0.501114s	0.013798s
0.498718s	0.015770s

So my method gives up to 30x performance than nlist! I'm happy to include saurik's nlist fix too, but it Bus Errored on strcmp too many times that I've gave up on that. Hopefully later it will be fixed.

Banning SCHelper from syslog

(Here is the necessary change required, for 2.2.1, if you don't bother to read.)

(Make sure you back up every file you want to change first. We won't take responsibility for your broken devices :p)

syslog is a very useful tool for watching variables and monitoring
system status. But SCHelper make it particular troublesome to follow the messages.

SCHelper stands to System Configuration Helper, and it manages the NSUserDefaults writes. In regular interval SCHelper will synchronize the NSUserDefaults on RAM to the harddisk, and report it in syslog. The problem is, the report takes 7 to 13 lines, and is completely useless to know:

May 9 15:55:16 --- SCHelper[1491]: per-session socket : invalidate fd 9
May 9 15:55:21 --- SCHelper[1491]: processing command "AUTH" w/data
May 9 15:55:21 --- SCHelper[1491]: sending status 0
May 9 15:55:21 --- SCHelper[1491]: processing command "PREFS open" w/data
May 9 15:55:21 --- SCHelper[1491]: sending status 0
May 9 15:55:21 --- SCHelper[1491]: processing command "PREFS lock/wait"
May 9 15:55:21 --- SCHelper[1491]: sending status 0
May 9 15:55:21 --- SCHelper[1491]: processing command "PREFS commit" w/data
May 9 15:55:21 --- SCHelper[1491]: sending status 0 w/reply
May 9 15:55:21 --- SCHelper[1491]: processing command "PREFS unlock"
May 9 15:55:21 --- SCHelper[1491]: sending status 0
May 9 15:55:21 --- SCHelper[1491]: processing command "PREFS close"
May 9 15:55:21 --- SCHelper[1491]: processing command "EXIT"


Usually one watches the syslog using tail -f /var/log/syslog. When SCHelper is in action, suddenly a dozen lines come up and you may miss what you need to know. (Of course you can filter the result using grep, but it's just pretending the problem does not exist.)

To solve the root cause we need to disable SCHelper from yelling. A starting point is to disassemble SCHelper. The file is located at /System/Library/Frameworks/SystemConfiguration.framework/SCHelper. We can search for the keyword processing command in the disassembly, and these line should come up:


+00104 000023c4 0100A0E3 mov r0,#0x1
+00108 000023c8 0710A0E3 mov r1,#0x7
+0010c 000023cc 98219FE5 ldr r2,[pc,#0x198] ; -> 0x256c CFSTR("processing command \"%s\"%s")
+00110 000023d0 960100EB bl SCLog (stub)


This is equivalent to the call SCLog(1, 7, CFSTR("processing command \"%s\"%s"), <other arguments>). What, yet another Log function? Hell yes.

This SCLog is an external symbol. We can play a dirty trick to transform all SCLog into ilogb :p. We need to edit the link table for this. The first obvious step is to search for the string _SCLog and replace it to _ilogb (or your favorite pure function). But this will make dyld complain not finding _ilogb in SystemConfiguration (_ilogb is in libSystem.B.dylib). We must change the dylib referenced by this particular symbol as well.

How dyld searches identify a stub symbol? From the Mach-O ABI, we can see it involves a lot of indirection:

1. Obtain the indirect symbol table from the dynamic symbol table (LC_DYSYMTAB load command)
2. Every entry of the indirect symbol table points to an index of the symbol table (LC_SYMTAB load command)
3. An entry of a symbol table is better known as nlist. In our case, the nlist contains reference to the dylib (an LC_LOAD_DYLIB load command) and an offset in the string table.
4. Finally from the string table we get the actual C string.

What we get is the offset of the C string, _SCLog. We can go up 1 level from there (to the nlist), and modify the dylib it references, then it should work.

For this task, otool and nm is of great help.

Using otool -L SCHelper we can see that the string table (LC_SYMTAB's stroff) is at file offset 15024 (0x3ab0). Additional, the file offset of the string _SCLog is at 0x3cd0. Therefore, the string table offset is 0x3cd0 - 0x3ab0 = 0x220.

Then, in the same load command we can find the symbol table's file offset (symoff) is 12832 (0x3220).

Now, to quickly search for a symbol, we use nm -p SCHelper | nl -v 0. (The -p flags tells nm don't try to sort the symbol table, and the nl part is a Unix utility for line numbering.) We can find _SCLog at 67, meaning we should be able to find the nlist of _SCLog at (0x3220 + 67 * sizeof(struct nlist) = 0x3544).

So let's proceed to 0x3544. The structure of nlist, for our concern is
struct nlist {
int symbol_index;
char lets_not_bother_it_its_always_0x0D;
char lets_not_bother_it_its_always_zero;
char lets_not_bother_it_its_always_0x01;
char the_dylib;
void* the_vm_address_that_we_dont_care;
};We can verify the first 4 bytes are indeed 0x220, so this is the correct address. For _SCLog, the_dylib = 2, and the dylib referenced are, in order:

1. /System/Library/Frameworks/CoreFoundation.framework/CoreFoundation
2. /System/Library/Frameworks/SystemConfiguration.framework/SystemConfiguration
3. /System/Library/Frameworks/Security.framework/Security
4. /usr/lib/libgcc_s.1.dylib
5. /usr/lib/libSystem.B.dylib

so we should change the 2 into 5.

I believe there is some link editor that doesn't require us to jump so many hoops. If you know, please leave a comment :).

In summary, the changes are (if you are using 2.2.1):

1. Open SCHelper with a hex editor.
2. Head to 0x354B, change the 02 to 05
3. Search for the string "SCLog", replace it with "ilogb".
4. Save, and of course, ldid it.

Now respring, and ps -A. Is SCHelper running? Yes, great. Does it emit useless syslog entries anymore? No, it's busy computing logarithms instead :p. Now launch Settings, fiddle with anything. Does it save? Yes, fantastic.

So our task succeeded. Note that if you are using any versions other than 2.2.1, the file offsets may be different.

GriP 0.1-11j released

This version introduced a lot of features since 0.1-11e (well you see there are 5 private development versions in between, the change is pretty a lot).

• Game mode – Suspend GriP in certain applications.
• Screen On/Off detection – Hold important messages when the screen is off, and show them all when the screen is on again.
• Multi-column support – Basically, you can fill a whole screen of GriP messages where you could only fill half before :p
• Theme customization – Currently you can only change the width of the Default theme, but the framework is completely general.

For developers, GriP now supports using Emoji as icon. For theme makers, the max width of the GriP message window can be queried using `+[GPMessageWindow maxWidth]`. The background colors of the window can be modified with `+[GPMessageWindow setBackgroundColor:]`, if you don't like to do that yourself.

You can download at http://code.google.com/p/networkpx/downloads/list as usual.

Introducing CFLog

In Foundation, there is a very handy printf-like function for debugging, called NSLog. You can call it like this:

NSLog(@"%@'s temperature is %f K", [NSDate date], 310.f);

In CoreFoundation, however, there is just a single-argument CFShow. This forces the simple NSLog line split into 3:

CFStringRef debugString = CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("%@'s temperature is %f K"), [NSDate date], 310.f);
CFShow(debugString);
CFRelease(debugString);

This is very annoying when you have lots of code like these. Of course we can always define a macro or function to take out all the repeating parts, e.g. in MobileSubstrate's source code:

#define CFLog(args...) \
    do { \
        CFStringRef string(CFStringCreateWithFormat(kCFAllocatorDefault, NULL, args)); \
        CFShow(string); \
        CFRelease(string); \
    } while(0)

But there is actually a more powerful CFLog built into CoreFoundation. It is, unsurprisingly, called CFLog:

/*
        APPLE SPI:  NOT TO BE USED OUTSIDE APPLE!
*/

enum { // Legal level values for CFLog()
    kCFLogLevelEmergency = 0,
    kCFLogLevelAlert = 1,
    kCFLogLevelCritical = 2,
    kCFLogLevelError = 3,
    kCFLogLevelWarning = 4,
    kCFLogLevelNotice = 5,
    kCFLogLevelInfo = 6,
    kCFLogLevelDebug = 7,
};

CF_EXPORT void CFLog(int32_t level, CFStringRef format, ...);

The header code can be found in http://www.opensource.apple.com/darwinsource/10.5.6/CF-476.17/CFLogUtilities.h (requires login). This is available on the iPhoneOS too as an undocumented function starting from 2.2. So you can now do it like this instead:

CFLog(kCFLogLevelDebug, CFSTR("%@'s temperature is %f K"), [NSDate date], 310.f);

Simple and beautiful.