Injecting commands and debugging a running Python program, with Project Euler example

How often has it happened to you… you build a simple script to calculate something, run some bulk process, and coming back after an hour or so it just hangs with no output. Is it doing something or stuck? You could debug it, using WinPdb or Visual Studio Code debugger or GDB to run it step by step, but that would lose the time that it has been processing. Instead, you can use Pyrasite, a program for looking in to a running Python script!

Installation and workarounds

Install Pyrasite for Python3 on Ubuntu using:

pip3 install pyrasite

Now if like me you do not have ~/.local/bin in PATH, you can just run it directly:

$ ~/.local/bin/pyrasite
 WARNING: ptrace is disabled. Injection will not work.
 You can enable it by running the following:
 echo 0 | sudo tee /proc/sys/kernel/yama/ptrace_scope
 usage: pyrasite [-h] [-l] [--gdb-prefix GDB_PREFIX] [--verbose]
                 [pid] [payload]
 pyrasite - inject code into a running python process
 positional arguments:
   pid                   The ID of the process to inject code into
   payload               The Python script to be executed inside the running
                         process. Can be one of the standard payloads (see
                         --list-payloads) or a filname.
 optional arguments:
   -h, --help            show this help message and exit
   -l, --list-payloads   List standard payloads
   --gdb-prefix GDB_PREFIX
                         GDB prefix (if specified during installation)
   --verbose             Verbose mode
 For updates, visit https://github.com/lmacken/pyrasite

Cool. The ptrace issue is a somewhat controversial decision for Ubuntu as documented here. Running that “echo 0…” command line it suggests, gets rid of that warning. (Note that on next reboot you would need to set that setting again). Now, if you have the “ID” number from the ID column of System Monitor, you can start up a shell as documented with the ID following the command:

~/.local/bin/pyrasite-shell 14134

but wait… no command line shell as described is shown? Why? It turns out the Pyrasite code is very old and not updated for recent GDB debugger. A simple one line fix is documented here and if you edit your local ~/.local/lib/python3.6/site-packages/pyrasite/injector.py to include that modified line:

 ' '.join(["-eval-command='call (void*) %s'" % cmd for cmd in gdb_cmds])),

It should now work and I can inject commands looking at the state of the running script:

$ ~/.local/bin/pyrasite-shell 14134
 Pyrasite Shell 2.0
 Connected to 'python3 ./Euler243.py'
 Python 3.6.9 (default, Oct  8 2020, 12:12:24) 
 [GCC 8.4.0] on linux
 Type "help", "copyright", "credits" or "license" for more information.
 (DistantInteractiveConsole)

>>> print(i)
924915  

>>> print(i)
925344                     

Project Euler example

The above example is using the following code that “should” find the answer to Project Euler 243.

from math import gcd

def R(denom):
    resilient = 0
    for i in range(1,denom):
        if gcd(i,denom) == 1:
            resilient += 1
    return resilient/(denom-1)
        
for i in range(2,10000000):
    #print('for %s is %s' % (i, R(i)))
    if R(i) < 15499/94744:
        print(i)
        exit()

Even after running this many hours, it had found less than a million resilient values. This is O(n^2) meaning each value is looking through each element – although the code above is working, there needs to be a faster way! It will get slower and slower with each new iteration.

One possible optimization would be to not go through every single one, but only those that have possibility of having numerator. This would save checks for numerous numerators but it appears this one is also not fast enough:

from math import gcd

primes = [2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,
607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,
739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,
1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,
1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,
1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,
1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,
1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,
1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,
1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,
1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,
2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,
2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,
2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,
2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,
2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,
2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,
2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,
2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,
2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,
2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,
2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,
2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,
3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,
3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,
3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,
3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,
3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,
3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,
3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,
3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,
3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,
3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,
3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,
3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,
4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,
4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,
4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,
4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,
4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,
4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,
4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,
4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,
4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,
4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,
4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,
4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,
5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,
5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,
5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,
5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,
5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,
5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,
5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,
5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,
5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,
5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,
5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,
5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,
6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,
6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,
6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,
6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,
6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,
6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,
6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,
6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,
6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,
6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,
6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,
7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,
7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,
7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,
7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,
7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,
7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,
7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,
7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,
7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,
7841,7853,7867,7873,7877,7879,7883,7901,7907,7919]

def R(denom):
    resilient = 0
    for i in range(1,denom):
        if gcd(i,denom) == 1:
            resilient += 1
    return resilient/(denom-1)
    
def smartR(denom):
    numerators = []
    for prime in primes:
        if prime > denom:
            break
        if denom % prime > 0:
            #Not divisible. look at fractions:
            for i in range(prime,denom,prime):
                if gcd(i,denom) == 1 and not i in numerators:
                    numerators.append(i)
    return (1+len(numerators))/(denom-1)
        
for i in range(2,1000000):
    # print('for %s is %s %s' % (i, R(i), smartR(i)))
    if smartR(i) < 15499/94744:
        print(i)
        exit()

It appears there is another trick that may be part of this one, it still takes too loong to run. So there is another trick to this one… here’s a hint, you will need to add more primes to get the accurate answer, I had to extend this list with list available online.

Open questions…

  1. What is the Big O notation of this optimized loop?
  2. What insight might speed this up or go about it in a different way?

Comments below:

Leave a Reply

Your email address will not be published. Required fields are marked *

× four = four