From an elevated (sysadmin privs) command prompt:
- slmgr.vbs /ipk XXXXX-XXXXX-XXXXX-XXXXX-XXXXX
to directly set the volume key,
SE Radio 652: Christian Mesh on OpenTofu
5 days ago
Thursday, October 11, 2012
Thursday, August 16, 2012
EMV SDA - Static Data Authentication
python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV 4.2 Book 2 - Security and Key Management
5 Static Data Authentication (SDA)
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV 4.2 Book 2 - Security and Key Management
5 Static Data Authentication (SDA)
Friday, August 3, 2012
EMV 4.2 Transaction Flow - Gen AC Layer
python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV 4.2 Book 3 - Application Specification
9 GENERATE AC Command Coding
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV 4.2 Book 3 - Application Specification
9 GENERATE AC Command Coding
EMV 4.2 Transaction Flow
EMV 4.2 Book 3
8 Transaction Flow EMV 4.2 Book 3
8.2 Example Flowchart Application Specification
EMV - Post Issuance Scripting
python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV 4.2 Book 3
6.5 Commands Application Specification
Post-Issuence Scripts
- Application Block
- Application Un-Block
- Card Block
- Pin Change / Un-Block
The post-issuance commands shall only be sent using script processing (see section 10.10) and secure messaging as specified in Book 2.
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV 4.2 Book 3
6.5 Commands Application Specification
Post-Issuence Scripts
- Application Block
- Application Un-Block
- Card Block
- Pin Change / Un-Block
The post-issuance commands shall only be sent using script processing (see section 10.10) and secure messaging as specified in Book 2.
EMV Transaction Flow / Process Summary - OS Choudry
2.2.2 Transaction Flow
[SELECT APPLICATION]
A transaction starts by selecting the desired application, which should be supported by both the card and the terminal. The command used for this purpose is SELECT, identi ed by CLA = 0x00 and INS = 0xA4. There are two ways to select an application: select by name using 1PAY.SYS.DDF01, or select by Application Identifier (AID). The former requires a further READ RECORD command (CLA = 0x00, INS = 0xB2) to select the applications under the directory 1PAY.SYS.DDF01, while the latter can select an application directly.
[GET PROCESSING OPTIONS - AFL, AIP]
Following application selection, the terminal will issue a GET PROCESSING OPTS command (CLA = 0x80, INS = 0xA8) which should retrieve the Application Interchange Profile (AIP) and Application File Locator (AFL). The AIP contains information about the type of authentication supported while the AFL tells the terminal which records (list of objects) should be read from the card to perform the transaction.
...
[READ RECORDS SPECIFIED IN AFL - CDOL1, CVM]
The next step is to read the records specified in the AFL by using the READ RECORD command. The most important objects are the Card Risk Management Data Object List 1 (CDOL1) and the Cardholder Verification Method (CVM) List. The CDOL1 specifies which data should be included in the first GENERATE AC command, while the CVM list enumerates the methods that can be used to authenticate the card user (e.g. PIN or signature). In the Chip and PIN system, as its name suggests, the most common CVM is the plain text PIN (there is an option to encipher the PIN but this is not used in the UK).
[GET PIN TRIAL COUNTER]
The next step of the transaction is to get the PIN try counter by means of the GET DATA command (CLA = 0x80, INS = 0xCA). The PIN try counter represents the number of trials the card user has to correctly enter the PIN before the card becomes locked (it can then be unlocked by the issuer bank). If the counter is greater than zero the user is asked to enter the PIN number into the numerical pad of the terminal. At this point the terminal can either verify the PIN online by requesting confirmation to the issuer bank, or ask the card (online) for confirmation. The most common method is the online version.
[VERIFY PIN]
Thus the next step is to send a VERIFY command (CLA = 0x00, INS = 0x20) to the card with plain text PIN as the command data. If the PIN is correct the card simply replies with a success status (SW1 = 0x90, SW2 = 0x00).
[GEN AC - REQUEST APPLICATION CRYPTOGRAM - USING CDOL1]
The last step of a transaction is to request an application cryptogram from the card using the GENERATE AC command (CLA = 0x80, INS = 0xAE).
This request may be for an Application Authentication Cryptogram (AAC) which requests canceling a transaction, an Authorization Request Cryptogram (ARQC) which request an online transaction (i.e. confirmation from issuer bank) or a Transaction Certificate (TC) which requests an offline transaction (i.e. no confirmation from the issuer bank).
The terminal sends a list of objects as specified by CDOL1 which generally includes the transaction amount, the Terminal Verification Results (TVR - 5 bytes indicating the status of the transaction as seen from the terminal perspective), the transaction date and an unpredictable number.
The card then uses its private key (only known by the card and the issuer bank) to compute a Message Authentication Code (MAC) over a set of bytes that include the data sent with the GENERATE AC command. If the card accepts the transaction it returns a MAC of the same type (AAC, ARQC or TC) or at a lower level (where AAC = level 1, ARQC = level 2 and TC = level 3). If the card decides to reject the transaction it will return a MAC of type AAC.
This request may be for an Application Authentication Cryptogram (AAC) which requests canceling a transaction, an Authorization Request Cryptogram (ARQC) which request an online transaction (i.e. confirmation from issuer bank) or a Transaction Certificate (TC) which requests an offline transaction (i.e. no confirmation from the issuer bank).
The terminal sends a list of objects as specified by CDOL1 which generally includes the transaction amount, the Terminal Verification Results (TVR - 5 bytes indicating the status of the transaction as seen from the terminal perspective), the transaction date and an unpredictable number.
The card then uses its private key (only known by the card and the issuer bank) to compute a Message Authentication Code (MAC) over a set of bytes that include the data sent with the GENERATE AC command. If the card accepts the transaction it returns a MAC of the same type (AAC, ARQC or TC) or at a lower level (where AAC = level 1, ARQC = level 2 and TC = level 3). If the card decides to reject the transaction it will return a MAC of type AAC.
[2nd GEN AC USING CDOL2]
In online transactions there may be a second GENERATE AC command issued by the terminal where the command data is according to CDOL2 instead of CDOL1. An illustration of the entire transaction flow is presented in figure 2.6.
Thursday, June 7, 2012
C# Dump to Text File
string text = "blah blah blah\nyak yak yak";
using (StreamWriter outfile = new StreamWriter("c:/dev/out.txt"))
{
outfile.Write(text);
}
Tuesday, May 22, 2012
Tuesday, March 20, 2012
Knight's Tour in C - Tom Wells
Finally, presenting the Knight's Tour in C - code by Tom Wells of tomwells.org.
Get the source from gitgub - git://github.com/drshade/knights-tour.git
Get the source from gitgub - git://github.com/drshade/knights-tour.git
#include
#include
#include
#include
#include
#define BOARDSIZE 5
#define THREADS 4
char referenceboard[BOARDSIZE * BOARDSIZE];
int solutions = 0, attempts = 0;
typedef struct { int x; int y; int valid; } position;
position new_position(int x, int y) { position p; p.x = x; p.y = y; p.valid = 1; return p; }
/* Code below unashamedly stolen from 'somewhere' to calculate difference (delta) between 2 timeval's */
int timeval_subtract (result, x, y) struct timeval *result, *x, *y;
{
if (x->tv_usec < y->tv_usec) {
int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
y->tv_usec -= 1000000 * nsec;
y->tv_sec += nsec;
}
if (x->tv_usec - y->tv_usec > 1000000) {
int nsec = (x->tv_usec - y->tv_usec) / 1000000;
y->tv_usec += 1000000 * nsec;
y->tv_sec -= nsec;
}
result->tv_sec = x->tv_sec - y->tv_sec;
result->tv_usec = x->tv_usec - y->tv_usec;
return x->tv_sec < y->tv_sec;
}
void hunt(position start, int depth, const char board[BOARDSIZE*BOARDSIZE])
{
attempts++;
char my_board[BOARDSIZE * BOARDSIZE];
memcpy(my_board, board, sizeof(my_board));
my_board[(start.x * BOARDSIZE) + start.y] = 1;
if (depth + 1 == BOARDSIZE * BOARDSIZE)
{
// Solution found
//
solutions++;
printf(".");
fflush(stdout);
if (solutions % 10000 == 0) printf("Found %d solutions so far...\n", solutions);
return;
}
// Determine possible moves
//
position possibles[8] = {
new_position(start.x - 1, start.y - 2), new_position(start.x - 2, start.y - 1),
new_position(start.x + 1, start.y - 2), new_position(start.x + 2, start.y - 1),
new_position(start.x + 1, start.y + 2), new_position(start.x + 2, start.y + 1),
new_position(start.x - 1, start.y + 2), new_position(start.x - 2, start.y + 1),
};
int x;
for (x = 0; x < 8; ++x)
{
// If position is within the bounds of the board, and not already taken, then hunt some more!
//
position* p = &possibles[x];
if (p->x >= 0 && p->y >= 0 && p->x < BOARDSIZE && p->y < BOARDSIZE && board[(p->x * BOARDSIZE) + p->y] == 0)
hunt(*p, depth + 1, my_board);
}
}
void* thread_start_function(void* arg)
{
int thread_num = (int)arg;
printf("[%d]", thread_num);
int skip = 0;
int x, y;
for (x = 0; x < BOARDSIZE; ++x)
for (y = 0; y < BOARDSIZE; ++y)
{
if (skip == thread_num)
{
printf("(%d,%d)", x, y);
hunt (new_position(x, y), 0, referenceboard);
}
skip++;
if (skip >= THREADS) skip = 0;
}
printf("<%d>", thread_num);
return 0;
}
int main(int argc, const char * argv[])
{
struct timeval start;
gettimeofday(&start, 0);
// Set board to zero
//
memset(referenceboard, 0, sizeof(referenceboard));
#if THREADS > 1
printf("[Multithreaded (%d)]\n", THREADS);
pthread_t threads[THREADS];
int x;
for (x = 0; x < THREADS; ++x)
pthread_create(&threads[x], NULL, thread_start_function, x);
for (x = 0; x < THREADS; ++x)
pthread_join(threads[x], NULL);
#else
printf("[Single threaded]\n");
int x, y;
for (x = 0; x < BOARDSIZE; ++x)
for (y = 0; y < BOARDSIZE; ++y)
{
printf("(%d,%d)", x, y);
hunt (new_position(x, y), 0, referenceboard);
}
#endif
struct timeval end;
gettimeofday(&end, 0);
struct timeval delta;
timeval_subtract(&delta, &end, &start);
printf("Found %d solutions in %ld.%ds (%d moves)\n", solutions, delta.tv_sec, delta.tv_usec, attempts);
return 0;
}
Sunday, March 18, 2012
Knight's Tour in Scala by Gary Pampara
Here is the Knight's Tour problem solved in Scala, by Gary Pampara.
object Problem { type Board = Array[Array[Boolean]] val boardsize = 5 val startingPositions = for { x <- (0 until boardsize) ; y <- (0 until boardsize) } yield (x,y) def legalasmoves(x: Int, y: Int) = { val possibles = List((x-1, y-2), (x-2,y-1), (x+1, y-2), (x+2, y-1), (x+1, y+2), (x+2, y+1), (x-1, y+2), (x-2, y+1)) possibles.filter(a => a._1 >= 0 && a._2 >=0 && a._1 < boardsize && a._2 < boardsize) }
def clone(x: Board) = { // Thanks Java :( val y = Array.fill(boardsize, boardsize)(true) for { i <- (0 until boardsize) j <- (0 until boardsize) } y(i)(j) = x(i)(j) y }
def availablemove(x: Int, y: Int, b: Board) = b(x)(y) def hunt(startx: Int, starty: Int, b: Board)(hist: List[(Int, Int)])(f: List[(Int, Int)] => Unit): Unit = { b(startx)(starty) = false if (hist.length == boardsize * boardsize) { print(".") f(hist) } else { val availablemoves = legalmoves(startx, starty).filter(a => availablemove(a._1, a._2, b)) availablemoves.foreach(a => hunt(a._1, a._2, clone(b))((a._1,a._2) :: hist)(f)) } }
def main(args: Array[String]) { val start = new java.util.Date() var solutions = List[List[(Int, Int)]]() def addSolution(a: List[(Int, Int)]) = { solutions = a :: solutions } startingPositions.par.foreach(pos => { print("(" + pos._1 + "," + pos._2 + ")") hunt(pos._1, pos._2, Array.fill(boardsize, boardsize)(true))(List((pos._1, pos._2)))(addSolution) }) val end = new java.util.Date() println((end.getTime() - start.getTime())/1000.0) println("Solutions: " + solutions.length) }}Friday, February 17, 2012
pyGForce - Force Directed Graphs in Python with NetWorkX and pyGTK
The latest little piece of handiwork that I would like to present is...
PyGForce - a force-directed graphing library that leverages current python technologies
- NetworkX python graph theory library
- python wrapper for GTK, pyGTK.
https://github.com/davidbarkhuizen/pygforce.git
End.
PyGForce - a force-directed graphing library that leverages current python technologies
- NetworkX python graph theory library
- python wrapper for GTK, pyGTK.
https://github.com/davidbarkhuizen/pygforce.git
 |
| Basic Force-Directed Graph |
 |
| And with Node Labelling |
End.
Saturday, January 28, 2012
Aggregated APDU List
python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils
Cheef's Grand APDU List Smartcard Selected Information APDU list
@ https://github.com/davidbarkhuizen/py_emv_utils
Cheef's Grand APDU List Smartcard Selected Information APDU list
#------------+------------------------+------------------------+----------------------+--------------------------------+ |ClaIns P1 P2|Lc Send Data |Le Recv Data | Specification | Description | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 04 | ISO 7816-9 6.3 | DEACTIVATE FILE | | A0 04 00 00 00 | 3GPP TS 11.11 | INVALIDATE | | A0 04 00 00 00 | SAGEM SCT U34 6.15 | INVALIDATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 0D xx xx 08 xxxx xxxx xxxx xxxx | SAGEM SCT U34 | VERIFY TRANSPORT CODE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 0C | ISO 7816-4 7.3.6 | ERASE RECORD (S) | | 80 0C 00 xx xx | SAGEM SCT U34 8.1.2 | CHECK (flash) | | 80 0C 01 xx xx | SAGEM SCT U34 8.1.2 | CHECK (EEPROM) | | 80 0C 02 xx xx | SAGEM SCT U34 8.1.2 | CHECK (checksum of file) | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 0E | ISO 7816-4 8.2.4 | ERASE BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 10 | ISO 7816-7 | PERFORM SCQL OPERATION | | 00 10 00 80 xx table name, ... | ISO 7816-7 7.1 | CREATE TABLE | | 00 10 00 81 xx view name, table name | ISO 7816-7 7.2 | CREATE VIEW | | 00 10 00 82 xx dictionary name | ISO 7816-7 7.3 | CREATE DICTIONARY | | 00 10 00 83 xx table name | ISO 7816-7 7.4 | DROP TABLE | | 00 10 00 84 xx view or dictionary | ISO 7816-7 7.5 | DROP VIEW | | 00 10 00 85 xx privileges | ISO 7816-7 7.6 | GRANT | | 00 10 00 86 xx privileges | ISO 7816-7 7.7 | REVOKE | | 00 10 00 87 xx data | ISO 7816-7 7.8 | DECLARE CURSOR | | 00 10 00 88 | ISO 7816-7 7.9 | OPEN | | 00 10 00 89 | ISO 7816-7 7.10 | NEXT | | 00 10 00 8A xx D, fixing N (columns)| ISO 7816-7 7.11 | FETCH | | 00 10 00 8B xx D, fixing N (columns)| ISO 7816-7 7.12 | FETCH NEXT | | 00 10 00 8C xx data | ISO 7816-7 7.13 | INSERT | | 00 10 00 8D xx data | ISO 7816-7 7.14 | UPDATE | | 00 10 00 8E | ISO 7816-7 7.15 | DELETE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 12 | ISO 7816-7 | PERFORM TRANSACTION OPERATION | | 00 12 00 80 | ISO 7816-7 8.2.1 | BEGIN | | 00 12 00 81 | ISO 7816-7 8.2.2 | COMMIT | | 00 12 00 82 | ISO 7816-7 8.2.3 | ROLLBACK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 14 | ISO 7816-7 | PERFORM USER OPERATION | | 00 14 00 80 xx User ID, ... | ISO 7816-7 9.2.1 | PRESENT USER | | 00 14 00 81 xx User ID, profile, ... | ISO 7816-7 9.2.2 | CREATE USER | | 00 14 00 82 xx User ID | ISO 7816-7 9.2.3 | DELETE USER | | 80 14 xx xx 00 | GEMPLUS MPCOS-EMV | Switch Protocol | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 16 00 00 xx MAC | VSDC | CARD BLOCK | | 80 16 0X 00 05 xxxx xxxx xx | GEMPLUS MPCOS-EMV | Freeze Access Conditions | | 84 16 0X 00 08 xxxx xxxx xxxx xxxx | GEMPLUS MPCOS-EMV | Freeze Access Conditions | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 18 00 00 xx MAC | VSDC | APPLICATION UNBLOCK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 1E 00 00 xx MAC | VSDC | APPLICATION BLOCK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 20 | ISO 7816-4 8.5.5 | VERIFY | | 00 20 00 80 08 xxxx xxxx xxxx xxxx | VSDC | VERIFY (Transaction PIN data) | | A0 20 00 xx 08 CHV Value | 3GPP TS 11.11 | VERIFY | | A0 20 00 xx 08 CHV Value | SAGEM SCT U34 6.10 | VERIFY | | 80 20 00 xx 08 ADM Value | SAGEM SCT U34 8.1.4 | VERIFY ADM | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 21 00 xx 08 ADM Value | SAGEM SCT U34 8.1.4 | VERIFY ADM | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 22 | ISO 7816-4 8.5.10 | MANAGE SECURITY ENVIRONMENT | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 24 | ISO 7816-4 8.5.6 | CHANGE CHV | | 84 24 00 00 xx PIN data + MAC | VSDC | PIN CHANGE/UNBLOCK | | A0 24 00 xx 10 Old CHV, New CHV | 3GPP TS 11.11 | CHANGE CHV | | A0 24 00 xx 10 Old CHV, New CHV | SAGEM SCT U34 6.11 | CHANGE CHV | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 26 | ISO 7816-4 8.5.8 | DISABLE CHV1 | | A0 26 00 01 08 CHV1 value | 3GPP TS 11.11 | DISABLE CHV1 | | A0 26 00 01 08 CHV1 value | SAGEM SCT U32 6.12 | DISABLE CHV1 | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 28 | ISO 7816-4 8.5.7 | ENABLE CHV1 | | A0 28 00 01 08 CHV1 value | 3GPP TS 11.11 | ENABLE CHV1 | | A0 28 00 01 08 CHV1 value | SAGEM SCT U34 6.13 | ENABLE CHV1 | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 2A | ISO 7816-8 5.2 | PERFORM SECURITY OPERATION | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 2C | ISO 7816-4 8.5.9 | UNBLOCK CHV | | A0 2C 00 xx 10 Unblock CHV(PUK), New CHV | 3GPP TS 11.11 | UNBLOCK CHV | | A0 2C 00 xx 10 Unblock CHV(PUK), New CHV | SAGEM SCT U34 6.14 | UNBLOCK CHV | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 2E 00 0# 01 Data | 3GPP TS 11.11 | WRITE CODE STATUS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 32 00 00 03 Value to be added. | 3GPP TS 11.11 | INCREASE | | A0 32 00 00 03 Value to be added. | SAGEM SCT U34 6.9 | INCREASE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 39 | | java Authentificate User Comman| +------------+------------------------+------------------------+----------------------+--------------------------------+ | 44 | ISO 7816-9 6.4 | ACTIVATE FILE | | A0 44 00 00 00 | 3GPP TS 11.11 | REHABILIDATE | | A0 44 00 00 00 | SAGEM SCT U34 6.16 | REHABILIDATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 46 | ISO 7816-8 5.1 | GENERATE ASYMMETRIC KEY PAIR | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 50 xx xx 08 Host challenge 00 | GlobalPlatform | INITIALIZE UPDATE then [C0] | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 70 | ISO 7816-4 8.1.2 | MANAGE CHANNEL | | 00 70 xx xx xx | GlobalPlatform | MANAGE CHANNEL | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 78 00 03 xx | GlobalPlatform | END R-MAC SESSION | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 7A xx 01 xx Data and C-MAC, if needed | GlobalPlatform | BEGIN R-MAC SESSION | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 82 | ISO 7816-4 8.5.3 | EXTERNAL AUTHENTICATE | | 84 82 00 00 10 Host cryptogram and MAC | GlobalPlatform | EXTERNAL AUTHENTICATE | | 84 82 00 00 0A Authentication-related data | VSDC | EXTERNAL AUTHENTICATE | | 00 82 00 xx 06 Manual | GEMPLUS MPCOS-EMV | EXTERNAL AUTHENTICATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 | ISO 7816-4 8.5.2 | GET CHALLENGE | | 00 84 00 00 08 Rnd Num | VSDC | GET CHALLENGE | | 00 84 xx xx 08 Rnd Num | GEMPLUS MPCOS-EMV | GET CHALLENGE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 86 | ISO 7816-4 8.5.4 | GENERAL AUTHENTICATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 88 | ISO 7816-4 8.5.1 | INTERNAL AUTHENTICATE | | 00 88 XX xx 0A Manual | GEMPLUS MPCOS-EMV | INTERNAL AUTHENTICATE | | A0 88 00 00 10 RAND : Rnd num xx SRES( 4B) , Kc (8B) | 3GPP TS 11.11 | RUN GSM ALGORITHM | | A0 88 00 00 10 RAND : Rnd num xx SRES( 4B) , Kc (8B) | SAGEM SCT U34 6.17 | RUN GSM ALGORITHM | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 | ISO 7816-4 8.2.5 | SEARCH BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A2 | ISO 7816-4 8.3.5 | SEEK | | A0 A2 00 xx xx Pattern xx | 3GPP TS 11.11 | SEEK | | A0 A2 00 xx xx Pattern xx | SAGEM SCT U34 6.8 | SEEK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A4 | ISO 7816-4 8.1.1 | SELECT | | 00 A4 04 00 xx AID 00 | GlobalPlatform | SELECT | | 00 A4 00 xx xx File ID || Name 00 Manual | VSDC | SELECT | | A0 A4 00 00 02 File ID | 3GPP TS 11.11 | SELECT | | A0 A4 00 00 02 File ID | SAGEM SCT U34 6.1 | SELECT | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 A8 00 00 00 00 | VSDC | GET PROCESSING OPTIONS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 AE 00 xx Transaction-related data | VSDC | | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B0 | ISO 7816-4 8.2.1 | READ BINARY | | 00 B0 xx xx xx | GEMPLUS MPCOS-EMV | READ BINARY | | A0 B0 xx xx xx | 3GPP TS 11.11 | READ BINARY | | A0 B0 xx xx xx | SAGEM SCT U34 6.4 | READ BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B2 | ISO 7816-4 8.3.1 | READ RECORD | | 00 B2 xx 00 | VSDC | READ RECORD | | A0 B2 xx xx xx | 3GPP TS 11.11 | READ RECORD | | A0 B2 xx xx xx | SAGEM SCT U34 6.6 | READ RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B4 | | java Component Data | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B8 | | java Create Applet | +------------+------------------------+------------------------+----------------------+--------------------------------+ | BA | | java CAP end | +------------+------------------------+------------------------+----------------------+--------------------------------+ | BC | | java Component end | +------------+------------------------+------------------------+----------------------+--------------------------------+ | BE 04 Data | GEMPLUS GemClub-MEMO | READ | +------------+------------------------+------------------------+----------------------+--------------------------------+ | C0 | ISO 7816-4 8.6.1 | GET RESPONSE | | 00 C0 1C Key Info | GlobalPlatform | GET RESPONSE | | 00 C0 00 00 00 | VSDC | GET RESPONSE | | 80 C0 00 00 xx | GEMPLUS MPCOS-EMV | Get Info on Get Response | | 80 C0 02 A0 08 Chip SN | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A1 08 Card SN | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A2 08 Issuer SN | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A3 04 Iss.Ref.N | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A4 0D Chip Inf | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A5 xx Keys | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A6 02 Last DF/EF | GEMPLUS MPCOS-EMV | Get Info | | A0 C0 00 00 xx | 3GPP TS 11.11 | GET RESPONSE | | A0 C0 00 00 xx | SAGEM SCT U34 6.3 | GET RESPONSE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | C2 | ISO 7816-4 8.6.2 | ENVELOPE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | C4 | | java Delete Applets | +------------+------------------------+------------------------+----------------------+--------------------------------+ | CA | ISO 7816-4 8.4.1 | GET DATA | | 00 CA 00 xx xx MAC, if present | GlobalPlatform | GET DATA | | 80 CA xx xx xx | VSDC | GET DATA | +------------+------------------------+------------------------+----------------------+--------------------------------+ | D0 | ISO 7816-4 8.2.2 | WRITE BINARY | | 80 D0 xx xx xx Data to be written in EEPROM | VSDC | LOAD STRUCTURE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | D2 | ISO 7816-4 8.3.2 | WRITE RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | D6 | ISO 7816-4 8.2.3 | UPDATE BINARY | | A0 D6 xx xx xx Data to be written in EEPROM | 3GPP TS 11.11 | UPDATE BINARY | | A0 D6 xx xx xx Data to be written in EEPROM | SAGEM SCT U34 6.5 | UPDATE BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 D8 xx xx xx KEY Date (and MAC) 00 | GlobalPlatform | PUT KEY | | D8 | EMV | Set Card Status(personalization| +------------+------------------------+------------------------+----------------------+--------------------------------+ | DA | ISO 7816-4 8.4.2 | PUT DATA | | 00 DA xx xx xx Data | VSDC | PUT DATA | +------------+------------------------+------------------------+----------------------+--------------------------------+ | DC | ISO 7816-4 | UPDATE RECORD | | 00 DC xx xx xx Data (and MAC) | VSDC | UPDATE RECORD | | A0 DC xx xx xx Data to be written in EEPROM | 3GPP TS 11.11 | UPDATE RECORD | | A0 DC xx xx xx Data to be written in EEPROM | SAGEM SCT U34 6.7 | UPDATE RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | DE 04 Data | GEMPLUS GemClub-MEMO | UPDATE | | A0 DE 00 00 03 Data | 3GPP TS 11.11 | LOAD AoC(SICAP) | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E0 | ISO 7816-9 6.1 | CREATE FILE | | 80 E0 02 00 0C Manual | GEMPLUS MPCOS-EMV | CREATE FILE | | 80 E0 xx xx xx FCI length | 3GPP TS 11.11 | CREATE FILE | | 80 E0 xx xx xx FCI length | SAGEM SCT U34 | CREATE FILE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E2 | ISO 7816-4 8.3.4 | APPEND RECORD | | 80 E2 00 00 xx Record (and MAC) | GlobalPlatform | APPEND RECORD | | 00 E2 00 00 xx Record | VSDC | APPEND RECORD | | 00 E2 00 00 xx Record | GEMPLUS MPCOS-EMV | APPEND RECORD | | 00 E2 00 00 xx Record | 3GPP TS 11.11 | APPEND RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E4 | ISO 7816-9 6.2 | DELETE FILE | | 80 E4 00 00 xx TLV coded name | GlobalPlatform | DELETE FILE | | A0 E4 00 00 02 xx xx | 3GPP TS 11.11 | DELETE FILE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E6 | ISO 7816-9 6.5 | TERMINATE DF | | 80 E6 xx 00 xx Manual | GlobalPlatform | INSTALL | | A0 E6 xx xx 00 | 3GPP TS 11.11 | LOCK RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E8 | ISO 7816-9 6.6 | TERMINATE EF | | 80 E8 00 00 xx Record | GlobalPlatform | LOAD | | A0 E8 00 xx 10 Data | 3GPP TS 11.11 | READ DIRECTORY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 EA 00 00 xx Data | 3GPP TS 11.11 | CREATE BINARY | | 80 EA 00 00 xx Data | SAGEM SCT U34 | CREATE BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 EE 00 xx 00 | VSDC | WRITE LOCK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 F0 xx xx xx AID of Application (and MAC) | GlobalPlatform | SET STATUS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 F2 00 00 xx | 3GPP TS 11.11 | GET STATUS | | A0 F2 00 00 xx | SAGEM SCT U34 6.2 | GET STATUS | | 80 F2 xx xx | GlobalPlatform | GET STATUS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 F8 xx xx xx | SAGEM SCT U34 8.1.1 | DIR | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 FA 00 00 00 | 3GPP TS 11.11 | SLEEP | | A0 FA 00 00 00 | SAGEM SCT U34 6.18 | SLEEP | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 FB xx xx xx | SAGEM SCT U34 8.1.1 | DIR | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 FC xx xx 10 | SAGEM SCT U34 8.1.3 | READ INFO | +------------+------------------------+------------------------+----------------------+--------------------------------+ | FE | ISO 7816-9 6.7 | TERMINATE CARD USAGE | | 80 FE xx xx 00 | SAGEM SCT U34 | BLOW FUSE | +------------+------------------------+------------------------+----------------------+--------------------------------+
Tuesday, January 10, 2012
Dynamite Knight's Tour in F# - Tom Wells
An Ungodly Fast Solution in F# to the Knights Tour
I would suggest that you consider coding the solution up in F#, as my friend Tom Wells has done. His solution finds all solutions for the 5x5 board in under 5 minutes.
I would suggest that you consider coding the solution up in F#, as my friend Tom Wells has done. His solution finds all solutions for the 5x5 board in under 5 minutes.
let boardsize = 7
// Setup board in 2d array setting all elements to true
// ___________________
// |0,4|1,4|2,4|3,4|4,4| (x,y)
// |0,3|1,3|2,3|3,3|4,3|
// |0,2|1,2|2,2|3,2|4,2|
// |0,1|1,1|2,1|3,1|4,1|
// |0,0|1,0|2,0|3,0|4,0|
// -------------------
//
let referenceboard = Array2D.init boardsize boardsize (fun x y -> true)
let legalmoves x y =
// Generate every move (impossible or not)
//
let possibles = [(x - 1, y - 2); (x - 2, y - 1);
(x + 1, y - 2); (x + 2, y - 1);
(x + 1, y + 2); (x + 2, y + 1);
(x - 1, y + 2); (x - 2, y + 1);]
// Prune the ones falling outside of the board
//
possibles |> List.filter (fun (x, y) -> x >= 0 && y >= 0 && x < boardsize && y < boardsize)
// Is a particular move still available to us? ie not already used
//
let availablemove x y (board : bool[,]) =
board.[x,y] = true
let rec hunt startx starty (board : bool[,]) (history : List<(int*int)>) foundsolutionfunc =
// Mark the position we're at as being taken
//
board.[startx,starty] <- false
// Check if we have a solution (ie we've covered the entire board)
//
if history.Length = boardsize * boardsize then
foundsolutionfunc (history) |> ignore
else
// Calculate the set of available moves from this point, filtering by positions which we've already used
//
let availablemoves = legalmoves startx starty |> List.filter (fun (x,y) -> availablemove x y board)
// For each available move, recurse
//
for (x,y) in availablemoves do
hunt x y (Array2D.copy board) ((x,y) :: history) foundsolutionfunc
[<EntryPoint>]
let main args =
let starttime = System.DateTime.Now
let solutions = new System.Collections.Generic.List<System.Tuple<int,int>>()
for x in seq { 0 .. Array2D.length1 referenceboard - 1 } do
for y in seq { 0 .. Array2D.length2 referenceboard - 1 } do
printf "(%d,%d)" x y
hunt x y (Array2D.copy referenceboard) [(x,y)] (fun solution ->
solutions.Add(new System.Tuple<int,int>(x,y))
printf "."
)
let endtime = System.DateTime.Now
printfn "\nFound %d solutions (took %03f seconds)" solutions.Count (endtime - starttime).TotalSeconds
printfn "Enter to quit"
System.Console.In.ReadLine() |> ignore
0
Friday, January 6, 2012
EMV / Smart-Card Development with pyscard / python
python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV Resources
- EMV Entry on Wikipedia
ATR = Answer To Reset
Standard/Spec = ISO7816-3
OnLine ATR Byte String Parser
ATR @ Wikipedia
PySCard Resources
- Project @ SourceForge
pyscard on ubuntu
1. install pcscd : sudo apt-get install pcscd
2. start daemon : sudo /etc/init.d/pcscd start
PY_EMV_UTILS - python pyscard emv smartcard utilities
svn checkout svn://svn.code.sf.net/p/pyemvutils/code/trunk pyemvutils-code
@ https://github.com/davidbarkhuizen/py_emv_utils
EMV Resources
- EMV Entry on Wikipedia
ATR = Answer To Reset
Standard/Spec = ISO7816-3
OnLine ATR Byte String Parser
ATR @ Wikipedia
PySCard Resources
- Project @ SourceForge
pyscard on ubuntu
1. install pcscd : sudo apt-get install pcscd
2. start daemon : sudo /etc/init.d/pcscd start
PY_EMV_UTILS - python pyscard emv smartcard utilities
svn checkout svn://svn.code.sf.net/p/pyemvutils/code/trunk pyemvutils-code
Monday, January 2, 2012
The Knights Tour Problem - Multi-Processor Algorithmic Parallelism with Python
Resources
- Wikipedia Entry.
- Stefan Behnel's page [What the Chess Knight is Doing] features some handy info on the solution space.
A Knight's Tour is a traversal of an 8x8 chess-board by the Knight / Horse piece, where the Knight touches each and every square once and only once during the tour, and makes only its characteristic L-shaped legal moves.
The problem can be further generalised by varying board parameters - to produce arbitrarily sized square NxN grids, and also arbitrarily-sized rectangular NxM grids.
There is also the closely-related problem of finding closed tours - where the Knight must be in a position on the final square of its open tour to theoretically return again to the first square of that tour by a legal move [closing the tour].
The Knights Tour Problem is a specific instance of the more general problem of finding a Hamiltonian Path (i.e. a connected path that touches each vertex once and only once) [open tour problem], and a finding a Hamiltonian cycle [closed tour problem].
The Solution Space
NxN Square Board - Count of Open Undirected Tours
4x4 => 0
5x5 => 1728
6x6 => 6,637,920
7x7 => 165,575,218,320
8x8 => 19,591,828,170,979,904
Brute Force Solution Approach
A brute force approach is typically only practical in the case of the 5x5 board, and is not generally useful for the higher dimensional problems, due to the fact the the solution space explodes with increasing problem dimensions. From the Wikipedia entry: "For a regular 8x8 chess board, there are approximately 4×10^51 possible move sequences, and it would take an unfathomable amount of time to iterate through such a large number of moves."
The ration of solutions to possible move sequences is small.
A Useful Heuristic - Warnsdorff's Rule [Wikipedia]
Warnsdorff's rule is a heuristic method for finding a knight's tour. Briefly, one moves the knight according to the following rule: always proceed to the square from which the knight will have the fewest onward moves. It is, of course, possible to have two or more choices for which the number of onward moves is equal; there are various methods for breaking such ties, including one devised by Pohl and another by Squirrel and Cull. This rule may also more generally be applied to any graph. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time. The knight's tour is a special case. The heuristic was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorff in 1823.
Solution Description
A back-tracker / depth-first searcher was developed in Python 2.7.
A Definition of Back-Tracking from the Wikipedia:
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.
A Definition of State Space Search from the Wikipedia:
State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property.
Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second.
State space search often differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state.
A General Description of the Specific Back-Tracker Implementation
Essentially the tracker successively explores the state space, collecting solutions as it goes.
Considering the 5x5 grid case, and starting from a blank board:
It is first noted that there are 25 possible first moves than can be made, since the knight can be placed on any of the 5 x 5 = 25 squares.
From each of these 25 possible first moves, uniquely different (although sometimes symmetrical) second moves can be made. Now, the number of possible second moves is not the same for every possible first move, for example first moves to edge squares will have less possible second moves than first moves to the centre square (or centre squares, in the case of even-dimensioned square boards).
Then for each of the possible second moves, there are a number of possible third moves, and so on, until either the knight gets stuck or successfully untangles a Hamiltonian path.
Thus the solution space can be thought of as a tree structure, with the blank board as the root node, and each of the 25 possible first choices as nodes adjacent to the root node. Each of the possible second choices are then nodes adjacent to their respective first-choice nodes, and so on. Knight's tours will then be Hamiltonian paths of length 25 [= N^2 = NxN], and aborted attempts will correspond to shorter paths.
The back-tracker dynamically and successively generates this tree structure - exploring a particular branch, until a dead-end is reached, then back-tracking until the first unexplored branch is encountered, pruning the fully examined branch off the tree and discarding it to minimize persistence (memory/disc) utilisation, before continuing forward again to explore another remaining unexamined branch.
Parallelisation with Python's Multiprocessing Module
The Knights tour problem just screams parallelisation, but how to do this given the restrictions imposed by Python's crummy Global Interpreter Lock (GIL) on the language's support for true multi-threading ? With the standard library's multiprocessing module:
multiprocessing is a package that supports spawning processes using an API similar to the threading module. The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads. Due to this, the multiprocessing module allows the programmer to fully leverage multiple processors on a given machine. It runs on both Unix and Windows.
So, what multiprocessing actually gives you is a set of independent operating-system level processes, each with it's own Python VM, and some infrastructure for both passing objects and (save us) directly sharing memory between these distinct processes.
Design Pattern
The design I've chosen utilises a single co-ordinating process, which spawns agent processes that are responsible for the execution of the actual business of exploring the solution space.
In the simplest case each agent process is assigned a different first choice, and it generates, examines and prunes the branch associated with that specific first choice, communicating solutions found back to the co-ordinating process, and finally notifying it of completion (total exploration of assigned solution space).
When the co-ordinating process is informed of successfully termination of an agent process, it will then spawn a new agent and assign them to examine a different branch of the tree.
When all branches have been examined, the solution space can be considered exhausted and all solutions found, and the coordinating process will report to file, and terminate.
Communication between the coordinating processes and its agents is achieved via use of the duplex pipe object available in the multiprocessing module.
Test
The Test
Exhaustively searching for and identifying all 1728 Knight's Tours on the 5x5 board.
Test Machine
I5-4x2.3GHz-8MB = Intel i5-2410M 2.3GHz with 8 GB
Test Machine Syn features an Intel i5 array of 4 cores at 2.3 GHz, with 8 GB memory available, running 64bit Windows 7, and 32 bit Python 2.7.
The Results
Single Process, No Threading - Effectively 1 Core
First off, the performance of the basic unthreaded, singleton-process back-tracker.
Total Time = 1hr46mins = 106 mins = 6360 seconds
Total Solution Count = 1728
Average Rate of Solution Finding = 0.27 solutions per second
Average Time to Find Next Solution = 3.68 seconds per solution
1 Controller Core + 3 x Agent Cores
Total Time = 41 mins = 2460 seconds
Total Solution Count = 1728
Average Rate of Solution Finding = 0.70 solutions per second
Average Time to Find Next Solution = 1.42 seconds per solution
Comparison - Singleton Process versus Multi-Process [1 Controller, 3 Agents]
So, the question is, from a quantitative perspective, what gains have been achieved by parallelising the algorithm ?
Since the test machine has 4 cores available, and the algorithm uses one of them for co-ordination, and farms out the work to 3 agent processes, we expect to see about a 3-fold gain in speed / decrease in total time.
Actually Observed Performance Ratio = 6360 / 2460 ~ 2.59
Theoretical Maximum Performance Ratio = 3 [going from 1 to 3 worker cores]
So, overall our increase in performance is not too bad, we didn't quite achieve the maximum ratio of 3, but we're not too far off at 2.59. Quantitatively we have achieved ~ 86% of the maximum theoretically possible increase in performance.
POST SCRIPT
"So, overall our increase in performance is not too bad" - Unfortunately, this is a blatant lie, see the next post on this topic for damning details.
- Wikipedia Entry.
- Stefan Behnel's page [What the Chess Knight is Doing] features some handy info on the solution space.
A Brief Introduction to the Knight's Tour Problem
A Knight's Tour is a traversal of an 8x8 chess-board by the Knight / Horse piece, where the Knight touches each and every square once and only once during the tour, and makes only its characteristic L-shaped legal moves.
 |
| Open Knights Tour on 5x5 Board [Graphic Linked from Wikipedia Entry] |
The problem can be further generalised by varying board parameters - to produce arbitrarily sized square NxN grids, and also arbitrarily-sized rectangular NxM grids.
There is also the closely-related problem of finding closed tours - where the Knight must be in a position on the final square of its open tour to theoretically return again to the first square of that tour by a legal move [closing the tour].
 |
| Closed Knights Tour on 8x8 Board [Graphic Linked from Wikipedia Entry] |
The Knights Tour Problem is a specific instance of the more general problem of finding a Hamiltonian Path (i.e. a connected path that touches each vertex once and only once) [open tour problem], and a finding a Hamiltonian cycle [closed tour problem].
The Solution Space
NxN Square Board - Count of Open Undirected Tours
4x4 => 0
5x5 => 1728
6x6 => 6,637,920
7x7 => 165,575,218,320
8x8 => 19,591,828,170,979,904
Brute Force Solution Approach
A brute force approach is typically only practical in the case of the 5x5 board, and is not generally useful for the higher dimensional problems, due to the fact the the solution space explodes with increasing problem dimensions. From the Wikipedia entry: "For a regular 8x8 chess board, there are approximately 4×10^51 possible move sequences, and it would take an unfathomable amount of time to iterate through such a large number of moves."
The ration of solutions to possible move sequences is small.
A Useful Heuristic - Warnsdorff's Rule [Wikipedia]
Warnsdorff's rule is a heuristic method for finding a knight's tour. Briefly, one moves the knight according to the following rule: always proceed to the square from which the knight will have the fewest onward moves. It is, of course, possible to have two or more choices for which the number of onward moves is equal; there are various methods for breaking such ties, including one devised by Pohl and another by Squirrel and Cull. This rule may also more generally be applied to any graph. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time. The knight's tour is a special case. The heuristic was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorff in 1823.
Brute-Force / Depth First Search
Finding of All Open Tours
in 5 x 5 Case
A back-tracker / depth-first searcher was developed in Python 2.7.
A Definition of Back-Tracking from the Wikipedia:
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.
A Definition of State Space Search from the Wikipedia:
State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property.
Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second.
State space search often differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state.
A General Description of the Specific Back-Tracker Implementation
Essentially the tracker successively explores the state space, collecting solutions as it goes.
Considering the 5x5 grid case, and starting from a blank board:
It is first noted that there are 25 possible first moves than can be made, since the knight can be placed on any of the 5 x 5 = 25 squares.
From each of these 25 possible first moves, uniquely different (although sometimes symmetrical) second moves can be made. Now, the number of possible second moves is not the same for every possible first move, for example first moves to edge squares will have less possible second moves than first moves to the centre square (or centre squares, in the case of even-dimensioned square boards).
Then for each of the possible second moves, there are a number of possible third moves, and so on, until either the knight gets stuck or successfully untangles a Hamiltonian path.
Thus the solution space can be thought of as a tree structure, with the blank board as the root node, and each of the 25 possible first choices as nodes adjacent to the root node. Each of the possible second choices are then nodes adjacent to their respective first-choice nodes, and so on. Knight's tours will then be Hamiltonian paths of length 25 [= N^2 = NxN], and aborted attempts will correspond to shorter paths.
The back-tracker dynamically and successively generates this tree structure - exploring a particular branch, until a dead-end is reached, then back-tracking until the first unexplored branch is encountered, pruning the fully examined branch off the tree and discarding it to minimize persistence (memory/disc) utilisation, before continuing forward again to explore another remaining unexamined branch.
Parallelisation with Python's Multiprocessing Module
The Knights tour problem just screams parallelisation, but how to do this given the restrictions imposed by Python's crummy Global Interpreter Lock (GIL) on the language's support for true multi-threading ? With the standard library's multiprocessing module:
multiprocessing is a package that supports spawning processes using an API similar to the threading module. The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads. Due to this, the multiprocessing module allows the programmer to fully leverage multiple processors on a given machine. It runs on both Unix and Windows.
So, what multiprocessing actually gives you is a set of independent operating-system level processes, each with it's own Python VM, and some infrastructure for both passing objects and (save us) directly sharing memory between these distinct processes.
Design Pattern
The design I've chosen utilises a single co-ordinating process, which spawns agent processes that are responsible for the execution of the actual business of exploring the solution space.
In the simplest case each agent process is assigned a different first choice, and it generates, examines and prunes the branch associated with that specific first choice, communicating solutions found back to the co-ordinating process, and finally notifying it of completion (total exploration of assigned solution space).
When the co-ordinating process is informed of successfully termination of an agent process, it will then spawn a new agent and assign them to examine a different branch of the tree.
When all branches have been examined, the solution space can be considered exhausted and all solutions found, and the coordinating process will report to file, and terminate.
Communication between the coordinating processes and its agents is achieved via use of the duplex pipe object available in the multiprocessing module.
Test
The Test
Exhaustively searching for and identifying all 1728 Knight's Tours on the 5x5 board.
Test Machine
I5-4x2.3GHz-8MB = Intel i5-2410M 2.3GHz with 8 GB
Test Machine Syn features an Intel i5 array of 4 cores at 2.3 GHz, with 8 GB memory available, running 64bit Windows 7, and 32 bit Python 2.7.
The Results
Single Process, No Threading - Effectively 1 Core
First off, the performance of the basic unthreaded, singleton-process back-tracker.
Total Time = 1hr46mins = 106 mins = 6360 seconds
Total Solution Count = 1728
Average Rate of Solution Finding = 0.27 solutions per second
Average Time to Find Next Solution = 3.68 seconds per solution
1 Controller Core + 3 x Agent Cores
Total Time = 41 mins = 2460 seconds
Total Solution Count = 1728
Average Rate of Solution Finding = 0.70 solutions per second
Average Time to Find Next Solution = 1.42 seconds per solution
Comparison - Singleton Process versus Multi-Process [1 Controller, 3 Agents]
So, the question is, from a quantitative perspective, what gains have been achieved by parallelising the algorithm ?
Since the test machine has 4 cores available, and the algorithm uses one of them for co-ordination, and farms out the work to 3 agent processes, we expect to see about a 3-fold gain in speed / decrease in total time.
Actually Observed Performance Ratio = 6360 / 2460 ~ 2.59
Theoretical Maximum Performance Ratio = 3 [going from 1 to 3 worker cores]
So, overall our increase in performance is not too bad, we didn't quite achieve the maximum ratio of 3, but we're not too far off at 2.59. Quantitatively we have achieved ~ 86% of the maximum theoretically possible increase in performance.
POST SCRIPT
"So, overall our increase in performance is not too bad" - Unfortunately, this is a blatant lie, see the next post on this topic for damning details.
Subscribe to:
Posts (Atom)