Algorithms - Heaps

Heaps – Heap is a form of binary tree. Its underlying data structure can be a list with children nodes in 2k+1 and 2k+2 position It could be a max-heap or min-heap.

A max-heap is kind of heap with top node (root node) having the maximum value. At any index i, a max-heap would have element[i] greater than its children.

Heap (minheap) provide optimal time for all three – insert, findminimum, deleteminimum.

The children index (2i and 2i + 1) can found very easily as multiplying by 2 is nothing BUT LEFT SHIFT. Parent on the other hand(i/2) can be found using RIGHT SHIFT.

Priority queues are implemented using heaps. (min-heap).

MAX-HEAPIFY – This operation when done on a list A in position i i.e MAX-HEAPIFY(A,i) brings the ith element “downwards” (if it is smaller), so the subtree rooted at i obeys MAX HEAP PROPERTY.

Implementation of MAX-HEAPIFY in Python –

def max_heapify(A, i):   

    left = 2 * i + 1

    right = 2 * i + 2

    largest = i

    if left < len(A) and A[left] > A[largest]:

        largest = left

    if right < len(A) and A[right] > A[largest]:

        largest = right

    if largest != i:

        A[i], A[largest] = A[largest], A[i]

        max_heapify(A, largest)

The complexity of MAX-HEAPIFY is O(logn).

To build a MAX-HEAP, you run MAX-HEAPIFY on the lower nodes (having children) UPTO to the top node. There is no point in running MAX-HEAPIFY on bottommost children nodes.

So for array of size n, you run MAX-HEAPIFY from floor(n/2) till the top node (i.e n=0). Below is the implementation –

def buildmaxheap(list):

    i=int(len(list)/2)

    while (i>=0):

        max_heapify(list,i)

        i=i-1

The above is the fundamental step of heapsort.

Following steps are done in heapsort –

1)      Build max-heap (A)

2)      From last element to i=1, loop

3)      Exchange current element with A[0] //top most element.

4)      Reduce heap-size, so that the last element is disconnected.

5)      Run MAX-HEAPIFY(A,0)

Below is the implementation –

i = len(list)

list2 = []

while (i>0):

    list[i-1],list[0] = list[0],list[i-1]

    list2.append(list.pop())

    max_heapify(list,0)

    i = i-1

The complexity of heapsort is O(nlogn) as we running MAX-HEAPIFY O(logn)  (n-1) times.

SQL Server cell level encryption. Backup/Restore scenario. Lost DMK password scenario

----------------------------Steps to achieve cell level encryption---------------------------------------

--CREATE MASTER KEY ENCRYPTION BY
--PASSWORD = 'myPass'
--GO

--CREATE CERTIFICATE EncDemoCert
--   WITH SUBJECT = 'Enc Demo SSN Encryption';
--GO

--CREATE SYMMETRIC KEY EncDemoSSNKey
--    WITH ALGORITHM = DES
--    ENCRYPTION BY CERTIFICATE EncDemoCert;
--GO

--Alter table Customer add EncSSN varbinary(500) null


--OPEN SYMMETRIC KEY EncDemoSSNKey
--DECRYPTION BY CERTIFICATE EncDemoCert;
--UPDATE Customer
--SET [EncSSN] = EncryptByKey(Key_GUID('EncDemoSSNKey'), convert(varchar,SSN))
--CLOSE SYMMETRIC KEY EncDemoSSNKey

                           
select * from Customer


--OPEN SYMMETRIC KEY EncDemoSSNKey
--DECRYPTION BY CERTIFICATE EncDemoCert;
--select *
--, CONVERT(VARCHAR, DecryptByKey(EncSSN)) as test
--from Customer
--CLOSE SYMMETRIC KEY EncDemoSSNKey

--------------------------------------Backup Restore scenario---------------------------------------

Lets say the database where encryption is done needs to backed-up and restored. In a full-backup scenario, the DMK and symmetric keys are also automatically backed-up and restored in the target server.

However to use it the DMK has be regenerated using the following queries - 

OPEN MASTER KEY DECRYPTION BY PASSWORD = 'myPass'; 

ALTER MASTER KEY REGENERATE WITH ENCRYPTION BY PASSWORD = 'myPass_New';

CLOSE MASTER KEY; 

----------Backup Restore scenario - Source DB server DMK password lost-----------------

If the source server DMK password (myPass in this case) is lost, then a new password can be added to its database master key using the following query in the SOURCE server- 

ALTER MASTER KEY 

    ADD ENCRYPTION BY PASSWORD = 'myPass_New2'.

After the above query, take the backup of the database, restore it in the target server use the queries mentioned above in the "Backup Restore scenario" 

-----------------------------------------Side Note------------------------------------------------------

You have some data in SQL Server encrypted with cert > key > DMK. (all at DB level, not server level)
If you run the following 2 commands, SQL Server will not allow -
--DROP CERTIFICATE EncDemoCert
--DROP MASTER KEY

However if you run the following query
--DROP SYMMETRIC KEY EncDemoKey
the symm key will be deleted permanently and all the encrypted data can NEVER be recovered.

So it is always advisable to backup the certificate and keys to a physical file.

(https://msdn.microsoft.com/en-IN/library/ms178578.aspx)

WCF Security Notes

SYMMETRIC BINDING (WHEN ONLY SERVER HAS THE X509 CERT)

In case of derived key scenario –

2 keys are generated from symmetric key (derived keys). 1 key is used for encryption, while the other is used for signing. The client encrypt both derived keys.

      ASYMMETRIC BINDING ( BOTH CLIENT AND SERVER HAVE X509 CERT)

Although Derived keys can be used for Asymm binding as well, it will be of no use as Encryption and Signing are already happening with different keys.

If you want to use Asymmetric binding, you can ONLY do it via code. Only configuration will not suffice.

First create a custom binding inheriting from Binding class. Then add a BindingExtension and use that bindingextension in the endpoint binding configuration.

WCF by default uses SYMMETRIC KEY with DERIVED KEYS on. You cannot switch to make DERIVED KEYS off UNLESS you make a ‘custom binding’.

                                                     Best of both worlds – 

If negotiateServiceCredential=”true”, then the public key is given to the Client in the beginning of the transaction, however note that IT IS NOT INTEROPERABLE.

To make it interoperable, public key has to given to client by out-of-band mechanism.

Since client has the public key part of the certificate, it can verify the service (by the checking the trusted CA store). Client authenticates the server by using the <identity> element inside <client> element.

Note – Even if the ProtectionLevel of a operation is set to None, its body will be in clear text BUT its message header will have an encrypted section as client credentials are being passed.

Even if client has its own pvk key for authentication to service, WCF defaults to Symmetric binding with DERIVED keys. If you want to override this behavior (i.e use asymmetric binding), you have programmatically create a custom binding and use it client and service end.

Using Reflexil with ILSpy to add Debug lines in a deployed DLL/EXE. (without recompiling/redeploying)

Using Reflexil with ILSpy to add Debug lines in a deployed DLL/EXE. (without recompiling/redeploying)

This can be done by directly editing the IL.

For example – In the beginning of method “func1” we want to record the parameters using Debug.WriteLine to see in DbgView or by adding some other listeners.

Do the following steps –

         1)      Unzip IlSpy and Reflexil  (both latest version, so that they are compatible) in the same folder.

         2)      Open ILSpy, open the dll/exe and click on the ‘gear’ icon on the top right to open reflexil.

         3)      Navigate to the required method, in this case “func1”.

         4)      Go to “Instructions” tab.

         5)      Right-click to add instructions. (Ignore the offset, focus on inserting the instruction at the right            place).

         6)      Most of the instruction to add Debug lines are done using ldstr (load string to stack), ldarg.0              (load the 0^th (first) argument to stack), box (if it is value type/integer), call to Concat and                    WriteLine.

         7)      To load nth argument, use ldarg.s (as shown above in the above diagram).

         8)      nop is no instruction (probably ‘enter’).

         9)      If you are unclear of any instruction, just write the code and see it in Ilspy+Reflexil.

         10)   To load any property say “LastName” of any object say “Person”, use ‘callvirt’ (shown above).

Advanced Quartz.NET scenarios

To enable Quartz.NET internal logging, add the following to Quartz.Server.exe.config - 


1) Use the following <common> config section
  <common>
     <logging>
      <factoryAdapter type="Common.Logging.Log4Net.Log4NetLoggerFactoryAdapter, Common.Logging.Log4Net1213">
        <arg key="configType" value="INLINE"/>
      </factoryAdapter>
    </logging>
  </common>

2) <appender name="QuartzInternalLog" type="log4net.Appender.RollingFileAppender">
            <file type="log4net.Util.PatternString" value="Trace/QuartzInternalLogFile_%date{yyyyMMdd}.txt"/>
            <appendToFile value="true"/>
            <maximumFileSize value="1024KB"/>
     <maxSizeRollBackups value="1000" />
            <rollingStyle value="Size"/>
   <datePattern value="yyyyMMdd" />
   <staticLogFileName value="true" />
   <lockingModel type="log4net.Appender.FileAppender+MinimalLock" />
            <layout type="log4net.Layout.PatternLayout">
              <conversionPattern value="%d{HH:mm:ss} [%t] %-5p %c - %m%n"/>
            </layout>
    </appender>


3) <logger name="Quartz">
<level value="DEBUG" />
<appender-ref ref="QuartzInternalLog" />
    </logger>

(NO NEED TO ADD QUARTZINTERNALLOG TO ROOT LEVEL LOGGER. THIS IS TO KEEP QUARTZ INTERNAL LOG SEPARATE).



To enable clustering in Quartz.NET, add the following to Quartz.Server.exe.config - 

<quartz>
<add key="quartz.checkConfiguration" value="false"/>
  <add key="quartz.server.serviceName" value="ABC-Project-QuartzServer-UAT"/>
  <add key="quartz.server.serviceDisplayName" value="ABC-Project-QuartzServer-UAT"/>
  <add key="quartz.server.serviceDescription" value="ABC-Project-QuartzServer-UAT"/>
  <add key="quartz.scheduler.instanceName" value="ABCProjectScheduler"/>
  <add key="quartz.scheduler.instanceId" value = "AUTO"/>
  <add key="quartz.threadPool.type" value="Quartz.Simpl.SimpleThreadPool, Quartz"/>
  <add key="quartz.threadPool.threadCount" value="20"/>
  <add key="quartz.threadPool.threadPriority" value="Normal"/>
  <add key="quartz.plugin.xml.type" value="Quartz.Plugin.Xml.XMLSchedulingDataProcessorPlugin, Quartz"/>
  <add key="quartz.plugin.xml.fileNames" value="~/quartz_jobs.xml"/>
  <add key="quartz.scheduler.exporter.type" value="Quartz.Simpl.RemotingSchedulerExporter, Quartz"/>
  <add key="quartz.scheduler.exporter.port" value="555"/>
  <add key="quartz.scheduler.exporter.bindName" value="QuartzScheduler"/>
  <add key="quartz.scheduler.exporter.channelType" value="tcp"/>
  <add key="quartz.scheduler.exporter.channelName" value="httpQuartz"/>
  <add key="quartz.jobStore.type" value="Quartz.Impl.AdoJobStore.JobStoreTX, Quartz"/>
  <add key="quartz.jobStore.dataSource" value="default"/>
  <add key="quartz.jobStore.tablePrefix" value="QRTZ_"/>
  <add key="quartz.jobStore.clustered" value="true"/>

  <add key="quartz.jobStore.driverDelegateType" value="Quartz.Impl.AdoJobStore.SqlServerDelegate, Quartz"/>
  <add key="quartz.dataSource.default.provider" value="SqlServer-20"/>
  <add key="quartz.jobStore.useProperties" value="true"/>
  <add key="quartz.jobStore.misfireThreshold" value="600000" />
 
  <add key="quartz.dataSource.default.connectionStringName" value="QuartzStore"/>
  <add key="quartz.dataSource.default.connectionString" value="Data Source=MyServer;Initial Catalog=ABC_Project_quartz_scheduler;User ID=MyUser;Password=MyPass"/>
</quartz>


NOTE THE ABOVE SETTINGS CAN ALSO BE DONE IN Quartz.Config file but Quartz.Server.exe.config WILL TAKE THE PRECEDENCE. I personally like keeping all the settings in one place i.e. Quartz.Server.exe.config.

To prevent concurrent execution of the job, do the following steps - 

       1) Use the following attribute – [DisallowConcurrentExecution] in the job class

 2) Use the following misfire instruction:

<trigger>

      <cron>

        <name>LongRunningJobTrigger</name>

        <group>CronTriggerGroup</group>

        <description>CronTrigger description</description>

        <job-name>LongRunningJob</job-name>

        <job-group>QuartzJobLib</job-group>

        <misfire-instruction>DoNothing</misfire-instruction>

        <cron-expression>0 0/1 * 1/1 * ? *</cron-expression>

      </cron>

    </trigger>

     3) Default behavior would fire new job instance in a separate thread. We need to avoid that.

4) With the above approach, the below output is produced –  (with trigger every minute (60 sec), and each job taking 90 seconds)

[13396] 10/15/2015 1:16:00 AM 635804487114616685 Main Job Process - Start

[13396] 10/15/2015 1:16:00 AM 635804487114616685 Internal Job Process - Start

[13396] 10/15/2015 1:17:30 AM 635804487114616685 Internal Job Process - End

[13396] 10/15/2015 1:17:30 AM 635804487114616685 Main Job Process - End

[13396] 10/15/2015 1:18:00 AM 635804487114616723 Main Job Process - Start

[13396] 10/15/2015 1:18:00 AM 635804487114616723 Internal Job Process - Start

[13396] 10/15/2015 1:19:30 AM 635804487114616723 Internal Job Process - End

[13396] 10/15/2015 1:19:30 AM 635804487114616723 Main Job Process - End

[13396] 10/15/2015 1:20:00 AM 635804487114616724 Main Job Process - Start

[13396] 10/15/2015 1:20:00 AM 635804487114616724 Internal Job Process - Start

[13396] 10/15/2015 1:21:30 AM 635804487114616724 Internal Job Process - End

[13396] 10/15/2015 1:21:30 AM 635804487114616724 Main Job Process - End

[13396] 10/15/2015 1:22:00 AM 635804487114616725 Main Job Process - Start

[13396] 10/15/2015 1:22:00 AM 635804487114616725 Internal Job Process – Start

Note  from the above output

a)      The new job (ID) does not starts until the previous job is finished.

b)     The new job did not start at 1:17:30, instead it started at 1:18:00 (Because of the misfire instruction “DoNothing”)

5) Note misfire-instruction property is available only with CronTrigger (not with SimpleTrigger). My suggestion is to always use CronTrigger instead of SimpleTrigger.

Common Gotchas

                                                                   

                                                               Common Gotchas

1)   Extra character in Certificate Thumbprint – Go to Windows MMC, add the certificates snap-in (Ctrl M), select any certificate properties and copy-paste its thumbprint in notepad to see it.

https://support.microsoft.com/en-us/kb/2023835

2)     Enterprise library Semantic logging (out-of-process) service not logging anything – Restart the service.

3)     Enterprise library Semantic logging will not write anything if any one of the parameter passed is null. Example  -

this.WriteEvent(2, FirstName, LastName, EncSSN, City);

will not write if anything if just “City” is null. 

4) While configuring Quartz.NET scheduler with AdoNetJobStore (needed for clustered scenario), make sure no other instance of Quartz.NET scheduler is pointing to the same job store (database). Example - SIT Env Quartz.NET jobstore might be pointing to UAT Env. jobstore.

5) Sharing a folder in Windows will update the existing ACL list of the children folder. For example - Sharing the inetpub > "wwwroot" folder with read-only permissions for some colleagues removed "NetworkService" and "IIS_IUSRS" users from all its virtual directories physical folders. 

ReSubmitting messages from ServiceBus Deadletter queue

ReSubmitting messages from ServiceBus Deadletter queue

Resubmitting messages, which do not require any change, from deadletter queue is straightforward and can be done using Service Bus Explorer tool.

However if the messages need change (say for example – because of bug – there is a special character which needs to be stripped off from the messages), ServiceBusExplorer would not do it. This can be done by using a custom tool/program to retrieve the messages from deadletter queue, store it somewhere, do the necessary modification and push the message back to the service bus. (Note – The earlier deadletter messages should be deleted (received)).

The sample code for reading messages from deadletter queue can be taken the open source ServiceBusExplorer tool itself. Program below –

class Program

    {

        private static int MaxBufferSize = 262144; // 256 KB

        static void Main(string[] args)

        {

            Uri uri = new Uri(@"sb://" + ConfigurationManager.AppSettings["SbHost"] + "." + ConfigurationManager.AppSettings["Domain"] + "/" + ConfigurationManager.AppSettings["Namespace"]);

            TokenProvider tokenProvider = TokenProvider.CreateSharedAccessSignatureTokenProvider(ConfigurationManager.AppSettings["KeyName"], ConfigurationManager.AppSettings["SharedAccessKey"]);

            MessagingFactory factory = MessagingFactory.Create(uri, tokenProvider);

            SubscriptionClient subsClient = factory.CreateSubscriptionClient(ConfigurationManager.AppSettings["Topic"], ConfigurationManager.AppSettings["Subscription"] + "/$DeadLetterQueue");

            var listMessages = subsClient.PeekBatch(Convert.ToInt32(ConfigurationManager.AppSettings["PeekMessageCount"]));           

            foreach (var bm in listMessages)

            {

                string messageText = null;

                Stream stream = bm.GetBody<Stream>();

                var element = new BinaryMessageEncodingBindingElement

                {

                    ReaderQuotas = new XmlDictionaryReaderQuotas

                    {

                        MaxArrayLength = int.MaxValue,

                        MaxBytesPerRead = int.MaxValue,

                        MaxDepth = int.MaxValue,

                        MaxNameTableCharCount = int.MaxValue,

                        MaxStringContentLength = int.MaxValue

                    }

                };

                var encoderFactory = element.CreateMessageEncoderFactory();

                var encoder = encoderFactory.Encoder;

                var stringBuilder = new StringBuilder();

                var message = encoder.ReadMessage(stream, MaxBufferSize);

                using (var reader = message.GetReaderAtBodyContents())

                {

                    var settings = new XmlWriterSettings { Indent = true };

                    using (var writer = XmlWriter.Create(stringBuilder, settings))

                    {

                        writer.WriteNode(reader, true);

                    }

                }

                messageText = stringBuilder.ToString();

                Console.WriteLine(messageText);

                stream.Dispose();

                File.WriteAllText(ConfigurationManager.AppSettings["PathToStoreMessages"] + bm.MessageId + ".txt", messageText);

            }

        }

    }